에라토스테네스의 체로 소수 찾기

에라토스테네스의 체는 1부터 $N$까지의 수 중 소수를 한꺼번에 찾는 알고리즘이다.

하나의 수만 판별할 때는 제곱근을 이용한 소수 판별로 충분하지만, 범위 안의 소수를 모두 구해야 한다면 에라토스테네스의 체가 적합하다.

핵심은 2부터 $N$까지의 수를 소수 후보로 두고, 소수의 배수를 차례대로 지워 끝까지 남은 수만 소수로 취급하는 방식이다.

30 이하의 소수를 구한다고 가정해 보자.

1. 2는 소수이므로 남기고, 2의 배수를 지운다.
2. 다음으로 남은 3도 소수이므로, 3의 배수를 지운다.
3. 다음으로 남은 5도 소수이므로, 5의 배수를 지운다.

이 과정을 반복하면 30 이하에서 남는 수는 다음과 같다.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

왜 $\sqrt{N}$ 이하의 소수만 처리할까?

합성수 $k$는 두 자연수의 곱으로 나타낼 수 있다. 예를 들어 35는 $5 \times 7$이다.

두 수가 모두 $\sqrt{k}$보다 크면 두 수의 곱도 $k$보다 커진다. 따라서 $k$를 만드는 두 수 중 적어도 하나는 반드시 $\sqrt{k}$ 이하이다.

$N$ 이하의 합성수 $k$는 반드시 $\sqrt{k}$ 이하의 소인수를 가진다. $\sqrt{k} \le \sqrt{N}$이므로, $\sqrt{N}$ 이하의 소수로 배수를 지우면 $N$ 이하의 모든 합성수를 제거할 수 있다.

def sieve(n):
    if n < 2:
        return []

    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    i = 2
    while i * i <= n:
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
        i += 1

    return [i for i in range(2, n + 1) if is_prime[i]]

assert sieve(1) == []
assert sieve(30) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

배수를 지울 때는 해당 소수의 두 배부터 시작하지 않고, 그 소수를 자기 자신과 곱한 수부터 시작한다. 예를 들어 5를 처리할 때 10($5 \times 2$), 15($5 \times 3$), 20($5 \times 4$)은 이미 앞에서 지워졌으므로 25($5 \times 5$)부터 지운다.

시간 복잡도는 $O(N \log \log N)$이다. 1부터 $N$까지의 소수를 모두 구하거나, 같은 범위에서 여러 수의 소수 여부를 반복해서 확인할 때 활용할 수 있다.