선형 체¶

수 $n$이 주어졌을 때, 구간 $[2;n]$에 있는 모든 소수를 찾으십시오.

이 문제를 푸는 표준적인 방법은 에라토스테네스의 체를 사용하는 것입니다. 이 알고리즘은 매우 간단하지만, 실행 시간이 $O(n \log \log n)$입니다.

준선형 실행 시간(즉, $o(n)$)을 갖는 알고리즘이 많이 알려져 있지만, 아래에서 설명하는 알고리즘은 그 단순함 때문에 흥미롭습니다. 이 알고리즘은 고전적인 에라토스테네스의 체보다 조금도 더 복잡하지 않습니다.

게다가 여기서 제시하는 알고리즘은 부수적으로 구간 $[2; n]$에 있는 모든 수의 소인수분해를 계산하며, 이는 많은 실제 응용에서 유용할 수 있습니다.

이 알고리즘의 약점은 고전적인 에라토스테네스의 체보다 더 많은 메모리를 사용한다는 점입니다. 이 알고리즘은 $n$개의 수로 이루어진 배열이 필요한 반면, 고전적인 에라토스테네스의 체는 $n$비트의 메모리(32배 더 적은 양입니다)만 있으면 충분합니다.

따라서 설명한 알고리즘은 $10^7$ 정도 크기의 수까지만 사용하고, 그보다 큰 수에는 사용하지 않는 것이 합리적입니다.

이 알고리즘은 Paul Pritchard가 고안했습니다. 이는 (Pritchard, 1987: 글 끝의 참고 문헌을 보십시오)에 나오는 알고리즘 3.3의 변형입니다.

알고리즘¶

우리의 목표는 구간 $[2; n]$에 있는 모든 수 $i$에 대해 최소 소인수 $lp [i]$를 계산하는 것입니다.

또한 지금까지 찾은 모든 소수의 목록을 저장해야 합니다. 이를 $pr []$라고 부릅시다.

값 $lp [i]$를 0으로 초기화하는데, 이는 모든 수를 소수라고 가정한다는 뜻입니다. 알고리즘을 실행하는 동안 이 배열은 점차 채워집니다.

이제 2부터 $n$까지의 수를 차례로 살펴봅니다. 현재 수 $i$에 대해 두 가지 경우가 있습니다.

$lp[i] = 0$ - 이는 $i$가 소수라는 뜻, 즉 $i$의 더 작은 인수를 하나도 찾지 못했다는 뜻입니다.
따라서 $lp [i] = i$를 대입하고 $i$를 목록 $pr[]$의 끝에 추가합니다.
$lp[i] \neq 0$ - 이는 $i$가 합성수이고, 그 최소 소인수가 $lp [i]$라는 뜻입니다.

두 경우 모두 $i$로 나누어떨어지는 수들에 대해 $lp []$의 값을 갱신합니다. 하지만 우리의 목표는 모든 수에 대해 $lp []$ 값을 많아야 한 번만 설정하도록 이를 수행하는 방법을 익히는 것입니다. 다음과 같이 할 수 있습니다.

수 $x_j = i \cdot p_j$를 생각해 봅시다. 여기서 $p_j$는 $lp [i]$ 이하인 모든 소수입니다(이 때문에 모든 소수의 목록을 저장해야 합니다).

이 형태의 모든 수에 대해 새 값 $lp [x_j] = p_j$를 설정합니다.

이 알고리즘의 정당성과 실행 시간에 대한 증명은 구현 뒤에서 확인할 수 있습니다.

구현¶

const int N = 10000000;
vector<int> lp(N+1);
vector<int> pr;

for (int i=2; i <= N; ++i) {
    if (lp[i] == 0) {
        lp[i] = i;
        pr.push_back(i);
    }
    for (int j = 0; i * pr[j] <= N; ++j) {
        lp[i * pr[j]] = pr[j];
        if (pr[j] == lp[i]) {
            break;
        }
    }
}

정당성 증명¶

알고리즘이 모든 값 $lp []$를 올바르게 설정하며, 모든 값이 정확히 한 번씩 설정된다는 것을 증명해야 합니다. 그러면 알고리즘의 나머지 동작은 모두 분명히 $O (n)$에 수행되므로, 알고리즘은 선형 실행 시간을 갖게 됩니다.

모든 수 $i$는 다음 형태로 정확히 한 가지 표현을 가진다는 점에 주목하십시오.

$$i = lp [i] \cdot x,$$

여기서 $lp [i]$는 $i$의 최소 소인수이고, 수 $x$는 $lp [i]$보다 작은 소인수를 하나도 갖지 않습니다. 즉,

$$lp [i] \le lp [x].$$

이제 이것을 우리 알고리즘의 동작과 비교해 봅시다. 실제로 알고리즘은 위에서 제시한 형태의 수를 얻기 위해, 모든 $x$에 대해 곱할 수 있는 모든 소수, 즉 $lp [x]$ 이하의 모든 소수를 차례로 살펴봅니다.

따라서 알고리즘은 모든 합성수를 정확히 한 번씩 거치며, 그곳에 올바른 값 $lp []$를 설정합니다. Q.E.D.

실행 시간과 메모리¶

실행 시간 $O(n)$이 고전적인 에라토스테네스의 체의 $O(n \log \log n)$보다 낫기는 하지만, 둘 사이의 차이는 그리 크지 않습니다. 실제로 선형 체는 에라토스테네스의 체를 일반적으로 구현한 것과 거의 같은 속도로 실행됩니다.

구간 체(segmented sieve)처럼 최적화된 에라토스테네스의 체와 비교하면 훨씬 느립니다.

이 알고리즘에 필요한 메모리, 즉 길이 $n$의 배열 $lp []$와 길이 $\frac n {\ln n}$의 배열 $pr []$를 고려하면, 이 알고리즘은 모든 면에서 고전적인 체보다 못한 것처럼 보입니다.

하지만 이 알고리즘의 장점은 배열 $lp []$를 계산한다는 것이며, 이를 이용하면 구간 $[2; n]$에 속하는 임의의 수의 소인수분해를 그 소인수분해의 크기에 비례하는 시간에 구할 수 있습니다. 게다가 배열을 하나만 더 사용하면 소인수분해를 구할 때 나눗셈을 피할 수 있습니다.

모든 수의 소인수분해를 아는 것은 일부 문제에서 매우 유용하며, 이 알고리즘은 이를 선형 시간에 구할 수 있는 몇 안 되는 알고리즘 중 하나입니다.

참고 문헌¶

Paul Pritchard, Linear Prime-Number Sieves: a Family Tree, Science of Computer Programming, vol. 9 (1987), pp.17-35.