에라토스테네스의 체

설명

일반적으로 어떤 자연수 $n$이 소수인지 판별하는 가장 쉬운 방법은, $\sqrt{n}$까지의 자연수로 하나하나 나눠보면서 나누어 떨어지는지 판정하는 것인데, 이를 $1$부터 $n$까지 자연수에 대해 반복하면서 $n$ 이하 소수 리스트를 구하는 데에는 $O(n\sqrt{n})$만큼의 시간 복잡도를 요구한다.

에라토스테네스의 체(Sieve of Eratosthenes)는 이보다 소수를 구하는 효율적인 알고리즘이다. 구체적인 알고리즘은 다음과 같다.

1. $1$부터 $n$까지의 수를 나열한 후, 우선 1을 지운다.
2. 다음 수 $k$가 지워져있는지 확인한다.
   2-1. 이미 지워져있다면 그 다음 수 $k+1$로 넘어간다.
   2-2. 만약 지워져있지 않다면, $mk \leq n,\ 2 \geq m$을 만족하는 $mk$를 모두 지우고 다음 수 $k+1$로 넘어간다.
3. 위 2번 과정을 $k$가 $n$에 도달할 때까지 반복한다.
4. 위 과정이 끝난 후 남아있는 수가 바로 $n$ 이하 소수의 리스트이다.

위 과정을 통해 $n$ 이하 소수 리스트를 구하는 데 필요한 시간복잡도는 $O(n\log\log n)$라는 것이 알려져 있다. 이는 매우 큰 $n$에 대해서도 거의 $O(n)$에 근접하는 매우 효율적인 알고리즘이다.

구현

아래 코드는 에라토스테네스의 체를 이용해 100만 미만의 소수 리스트를 구하는 python 구현 코드이다.

MAX_NUM = 1000001

primes = []
visited = [False for _ in range(MAX_NUM)]

for num in range(2, MAX_NUM):
    if not visited[num]:
        primes.append(num)
        for next_num in range(2*num, MAX_NUM, num):
            visited[next_num] = True

print(primes)