에라토스테네스의 체 (소수판별 알고리즘) Python

에라토스테네스의 체 

소수를 구하는 알고리즘 문제에서 주로 사용되는 풀이 방식이다.

1. 2 ~ N 까지의 자연수들 중에서, 아직 지워지지 않은 수들 중에서 가장 작은 수를 찾는다. 이를 p 라고 한다.

2. p는 소수이므로 지우지 않고 남겨준다.

3. p 의 배수들을 하나씩 지워나간다. 

1 ~ 3 의 과정들을 반복하면 결국 소수들만 남게 된다. 

ex) 2는 소수이므로 지우지 않고 , 4, 6, 8 ... 은 지워나가기 

위의 그림을 참고하면 이해가 빠르다 

N = 1000000
primes = [True] * (N+1) # 소수
primes[0] = False # 0 은 자연수 아님
primes[1] = False # 1은 소수 될 수 없음

for i in range(2, N+1):
    if primes[i]:
        for j in range(2*i, N+1, i): # i 의 배수들을 지우기
            primes[j] = False

 

중복 계산을 줄이고 더 효율적으로 구하기 위해서는 제곱근까지만 확인해주면 된다. 제곱근까지만 지우는 이유는 자신의 제곱수를 넘어가는 배수부터는 이미 이전이 지워졌기 때문이다. 따라서 제곱수 그 이상의 수를 검사할 필요가 없다. 

 

INF = 1000000
primes = [True] * (N+1) # 소수
primes[0] = False # 자연수 아님
primes[1] = False # 소수 될 수 없음
M = N**0.5
for i in range(2, M+1):
    if primes[i]:
        for j in range(i*i, N+1, i): # i 의 배수들을 지우기
            primes[j] = False

 

예를 들어서 N = 16 일때 

i == 2이면 
4 6 8 10 12 14 16 이 지워진다. 
i == 3 이면
9 12 15

16의 제곱근 4 이하로만 지워주었는데, 

[2, 3, 5, 7, 11, 13]

이렇게 소수들만 남게 된다.