🔍문제

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	122753	57684	46448	47.092%

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1 복사

4
1 3 5 7

예제 출력 1 복사

3

📝내 풀이

number = int(input())
number_arr = list(map(int, input().split()))

prime_number_arr = list(range(max(number_arr) + 2))
prime_number_arr[1] = 0

for i in range(2, len(prime_number_arr)):
    if prime_number_arr[i] == 0:
        continue
    for j in range(2, (max(number_arr)//i)+1): # i 의 배수들 제거
        if prime_number_arr[i*j] == 0:
            continue
        prime_number_arr[i*j] = 0
            
print(len(set(number_arr) & set(prime_number_arr)))

소수란 자기 자신으로 밖에 나누어 떨어지지 않는 수이기 때문에 간단하게 자기 자신으로 나워서 나머지가 0이면 소수라 판단하면 되지만 에라토스테네의 체 알고리즘을 사용할 경우엔 그리 간단하진 않다. 에라토스테네의 체의 알고리즘은 2부터 시작하여 기준이 되는 숫자의 배수를 지우면서 소수를 찾는 방법이다. number_arr 라는 별도의 리스트에 기준 수의 배수를 0으로 지우는 작업을 반복하여 마지막까지 지워지지 않은 숫자들의 개수로 답을 출력한다.

참고

• 에라토스테네스의 체

BOJ 카테고리 내 다른 글 보러가기