[Algorithm] 소수 구하기: 에라토스테네스의 체 ( Sieve of Eratosthenes )

어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 된다.

시간복잡도: O(N^1/2)

 

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

1. 배열을 생성하여 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

[참고]

velog.io/@max9106/Algorithm-에라토스테네스의-체

 

[코드]

 

import sys
import math
import itertools

N_input = int(sys.stdin.readline())
line = list(map(int, sys.stdin.readline().split(" ")))
N = [1]* 1001 # 0이면 합성수 1이면 소수

N[1] = 0
# 체 만들기
for i in range(2, 32):
    if N[i] == 0:
        continue
    num = i
    num *= 2
    while num < 1001:
        N[num] = 0
        num += i
# print(N)
count = 0
for num in line:
    if N[num] == 1:
        count += 1