백준 1978번: 소수 찾기

문제

문제 바로가기 > 백준 1978번: 소수 찾기

풀이

범위에서 합성수를 지우는 방식으로 소수를 찾는 방법인 "에라토스테네스의 체"를 이용해서 풀었다. 자세한 과정은 다음과 같다.

1. 1은 소수가 아니므로 제거함.
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지움.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지움.
4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지움.
5. 위 과정을 범위 내에서 반복함.

list_one_to_thousand = [i for i in range(1001)]
list_one_to_thousand[1]=0
for i in range(2, 1001):
    if list_one_to_thousand[i]!=0:
        for j in range(2, 501):
            remove = i*j
            if(remove<=1000):
                list_one_to_thousand[remove] = 0
            else:
                break
N = int(input())
input_list = list(map(int, input().split()))
ans = 0
for tmp in input_list:
    if list_one_to_thousand[tmp]!=0:
        ans+=1
print(ans)

나 같은 경우에는 idx와 element가 같은 배열 (0~1000)을 선언하고, 에라토스테네스의 체를 적용하여 소수가 아닌 경우 0으로 바꿔주었다. 그럼 나중에는 입력을 받아서 0이 아닌 경우만 카운트해주면 된다.