[Python] 소수 구하기 (에라토스테네스의 체)

소수란 1과 자기 자신만을 가지는 정수입니다. 소수를 구하는 알고리즘은 많지만 여기서 설명하는 알고리즘은 에라토스테네스의 체라고 불리는 알고리즘입니다. 에라토스테네스는 고대 그리스의 수학자로서 마치 체로 걸러 내는 것처럼 수를 걸러 낸다고 하여 에라토스테네스의 체라고 부릅니다.

이 방법은 아주 단순하지만 소수를 구하는데 효과적인 방법입니다.

원리

숫자 1 ~ 120 범위 안에 있는 소수를 모두 계산한다고 가정합니다.

1. 1은 소수도, 합성수도 아닌 기초수이기 때문에 1을 제거합니다. 
   
2. 2는 소수이므로 2를 다른 곳에 기록합니다.
3. 자기 자신(2)를 제외한 2의 배수를 모두 지웁니다.
4. 남아있는 수에서 2 다음인 수인 3부터 진행을 시작합니다.
5. 3은 소수이므로 2를 기록한 곳에 기록합니다.
6. 자기 자신(3)을 제외한 3의 배수를 모두 지웁니다.
7. 3 다음의 수는 4이지만 2의 배수로 2번에서 지워졌으므로 남아있는 수에서 3 다음인 수인 5부터 진행을 시작합니다.
8. 5은 소수이므로 2와 3을 기록한 곳에 기록합니다.
9. 자기 자신(5)를 제외한 5의 배수를 모두 지웁니다.
10. 위의 과정을 끝까지 반복하면 구하는 구간의 모든 소수가 남습니다.
    

위의 과정은 구하고자 하는 120까지의 수를 계속해서 지워나가는 방식입니다. 이 방식은 소수를 확실하게 구할 수 있지만 시간복잡도가 O(n^2)이 발생합니다. 여기서 에라토스테네스의 체를 이용하면 계산하는 범위를 줄일 수 있습니다.

에라토스테네스의 공식은 위 과정을 120까지 할 필요 없이 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 소수를 구할 수 있습니다. 따라서 위의 경우, 2, 3, 5, 7의 배수를 지우고 남은 수는 모두 소수입니다.

즉, 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없습니다. 120에 루트를 씌우면 10.954451150103322의 값이 나오는데 이는 11보다 작으므로 11이하의 배수만 체크해도 소수를 구할 수 있습니다. 

코드

import math def get_primes(n): # 구하고자 하는 수만큼 True를 갖는 리스트 생성 is_primes = [True] * n # n의 최대 약수가 sqrt(n) 이하이므로 계산한 후, 소숫점이 있을 경우 올림으로 최대 반복 횟수 계산 max_length = math.ceil(math.sqrt(n)) for i in range(2, max_length): # True일 경우, 소수 if is_primes[i]: # i이후 i의 배수들을 지워나감 for j in range(i+i, n, i): is_primes[j] = False # 리스트의 True로 남아 있는 인덱스(소수)를 추출 return [i for i in range(2, n) if is_primes[i]] a = get_primes(10) print(a)