에라토스테네스의 체

에라토스테네스의 체는 소수가 아닌 것을 걸러내어 소수 집합을 구하는 방법이다. 어떤 자연수의 배수는 소수가 아님을 이용한다.

소수인지 여부를 담은 배열 $S$를 준비한 뒤, for문으로 2부터 순회하면서 $i$가 아닌 $i$의 배수를 $S$에서 지우면 된다.

소수의 배수는 소수가 아님을 이용하여 $i$가 소수일 때만 지우는 식으로 시간을 줄일 수 있다.

S = [1 for i in range(n + 1)]
P = []
for i in range(2, n + 1):
    if S[i]:
        for j in range(2, n // i + 1):
            S[i * j] = 0
        P.append(i)

에라토스테네스의 체의 시간복잡도는 $O(n \log{\log{n}})$임이 알려져 있다.

에라토스테네스 체의 단점

에라토스테네스의 체는 소수 $p$에 대해 $p$의 배수를 전부 체크한다. 따라서 어떤 수 $n$은 그 소인수의 개수만큼 탐색하게 된다. 예를 들어 2310은 2, 3, 5, 7, 11 총 5번을 탐색한다.

오일러의 체 (Linear Sieve)

오일러의 체는 위의 단점을 보완한 방법으로, 모든 수가 한 번씩만 처리된다. 각 수의 가장 작은 소인수(이하 최소 인수)를 이용한다.

어떤 수 $n$의 최소 인수를 $spf(n)$라고 하면 자연수 $i$에 대해 다음과 같이 표현할 수 있다.

위 식을 만족하는 $i$는 $n$에 대해 유일하며, $n$의 최소 인수가 $spf(n)$이므로 $spf(i) \geq spf(n)$이다.

이 관계를 거꾸로 생각하면, 어떤 수 $i$에 $spf(i) \geq p$인 소수 $p$를 곱하면 최소 인수가 $p$인 수 $n$을 얻을 수 있다.

$n$에 대한 $i$가 유일하기 때문에, 어떤 수 $n$는 서로 다른 조건에서 (서로 다른 $i$에 대해) 두 번 이상 탐색되지 않는다.

for문으로 $i$를 순회하며 위 식을 적용하면 모든 $n$를 딱 한 번만 탐색하여 $spf$ 배열을 구할 수 있다.

spf = [0] * (n + 1)
P = []

for i in range(2, n + 1):
    if spf[i] == 0:
        P.append(i)
        spf[i] = i
    for p in P:
        if p > spf[i] or i * p > n:
            break
        spf[i * p] = p

$i$를 $n$까지 탐색하고, 각 $i$에 대해 $n = i \times spf(n)$인 모든 $n$를 탐색하므로 $n$ 이하의 모든 자연수에 대해 탐색할 수 있다. $n = ip$에 대해 위 범위에 포함되지 않는 경우가 없음을 보임으로써 증명할 수 있다.

또한 각 자연수가 모두 한 번씩 탐색되므로 $O(n)$이다.

오일러 체를 이용한 소인수 분해

오일러 체를 이용해 spf[]를 구했다고 하자. $n$을 소인수 분해 하는 방법은 $n$부터 재귀적으로 $spf$를 찾는 것이다. 예를 들어 2310을 소인수 분해하는 과정은 다음과 같다.

spf(2310) = 2
spf(2310 / 2) = spf(1155) = 3
spf(1155 / 3) = spf(385) = 5
spf(385 / 5) = spf(77) = 7
spf(77 / 7) = spf(11) = 11

>>> 2×3×5×7×11

while n > 1:
    print(spf[n])
    n //= spf[n]

$n$의 소인수의 개수만큼 탐색한다. $n$의 소인수의 개수가 가장 많은 경우는 $n = 2^k$꼴인데 이 경우 $k = \log{n}$번 처리하므로, 자연수 $n$의 탐색 횟수는 $\log{n}$을 넘지 않는다. 따라서 소인수 분해의 시간복잡도는 $O(\log{n})$이다.