[알고리즘] 에라토스테네스의 체

에라토스테네스의 체는 소수(prime number)를 구할 때 가장 기본적으로 사용되는 알고리즘 입니다.

 

소수를 구하는 것은 기본적으로 완전탐색을 사용하는데, 이미 검사한 수는 스킵하여 효율성을 높였습니다.

+ 소수는 0과 1을 제외한 2부터 시작됩니다. 코드에서 prime[0], prime[1]이 True여도 이는 소수가 아니므로 사용할 때 주의해야 합니다.

 

파이썬 코드

N = 10000 # N-1번까지의 소수 구하기
prime = [True]*(N+1)
for i in range(2, int(N**0.5)): # 2 부터 N-1의 제곱근 까지 검사
    if prime[i]:
        for j in range(i+i, N+1, i):
            prime[j] = False

 

매우 간단하지만 막상 사용하려고 하면 쉽게 떠오르지 않습니다