에라토스테네스의 체

정의. 양의 정수가 서로 다른 자연수 약수를 정확히 두 개, 즉 1과 자기 자신만을 가질 때 그 수를 소수라고 합니다. 1은 소수로 간주하지 않습니다.

에라토스테네스의 체(영어: sieve of Eratosthenes)는 $1$부터 $n$까지의 모든 소수를 찾는 알고리즘입니다.

기본 아이디어는 알고리즘의 이름 그대로입니다. 수 $1, 2,\ldots, n$을 차례로 적은 다음, 다음과 같이 지워 나갑니다.

• 먼저 $2$ 자신을 제외한, $2$로 나누어떨어지는 수들을,
• 그다음 $3$ 자체를 제외하고 $3$으로 나누어떨어지는 수를,
• $4$의 배수는 이미 지웠으므로 아무것도 하지 않으며,
• 그다음 $5$ 자체를 제외하고 $5$로 나누어떨어지는 수들을 계속 지워 나갑니다,

…그리고 이와 같이 계속합니다.

가장 간단한 구현은 다음과 같을 수 있습니다:

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    for (int i = 2; i <= n; i++)
        if (is_prime[i])
            for (int j = 2 * i; j <= n; j += i)
                is_prime[j] = false;
    return is_prime;            
}

이 코드는 먼저 0과 1을 제외한 모든 수를 소수로 표시한 다음, 합성수를 걸러 내는 과정을 시작합니다. 이를 위해 반복문에서 $2$부터 $n$까지의 모든 수를 차례로 살펴보고, 현재 수가 소수이면 그 수의 배수를 모두 합성수로 표시합니다.

메모리가 허용한다면, 속도를 최적화하기 위해 bool 벡터 대신 char 벡터를 사용하는 것이 좋습니다. 다만 이 경우 8배 더 많은 공간을 차지합니다. 컴퓨터는 비트를 직접 다룰 수 없기 때문에, vector<bool>에 인덱스로 접근할 때 먼저 필요한 바이트를 가져온 다음 비트 연산으로 필요한 값을 얻으며, 이 과정에 상당한 시간이 걸립니다.

#실행 시간

알고리즘의 점근적 실행 시간이 적어도 $O(n \log n)$보다 나쁘지 않다는 것은 꽤 쉽게 보일 수 있습니다. 각 수가 소수인지 먼저 확인하지 않고 모든 수에 대해 지우기 루프에 들어간다고 하더라도, 전체 반복 횟수는 다음과 같을 것입니다.

여기서는 조화급수의 점근적 성질을 이용했습니다.

원래 알고리즘의 점근적 복잡도는 이보다 더 좋아야 합니다. 이를 더 정확하게 구하려면 소수에 관한 두 가지 사실이 필요합니다:

1. $1$부터 $n$까지의 소수는 대략 $\frac{n}{\ln n}$개입니다.
2. 소수는 큰 「간격」이나 「밀집」 없이 분포되어 있습니다. 즉, $k$번째 소수는 대략 $k \ln k$와 같습니다.

간단히 말해, 수 $k$가 $\frac{1}{\ln n}$의 「확률」로 소수라고 생각할 수 있습니다. 그러면 알고리즘의 실행 시간을 더 정확하게 다음과 같이 추정할 수 있습니다.

알고리즘의 점근적 복잡도는 $O(n)$까지 더 개선할 수 있습니다.

#선형 체

에라토스테네스의 체의 주된 문제는 일부 수를 합성수로 여러 번 표시하게 된다는 점입니다. 그 횟수는 해당 수가 가진 서로 다른 소인수의 개수만큼입니다. 선형 실행 시간을 달성하려면 모든 합성수를 정확히 한 번씩만 살펴보는 방법을 고안해야 합니다.

수 $k$의 최소 소인수를 $d(k)$라고 하고, 다음 사실에 주목합시다. 합성수 $k$는 $k = d(k) \cdot r$이라는 유일한 표현을 가지며, 이때 수 $r$에는 $d(k)$보다 작은 소인수가 없습니다.

최적화의 아이디어는 이 $r$을 순회하면서, 각 $r$에 대해 필요한 인수만, 즉 $2$부터 $d(r)$까지(포함)의 모든 인수만 순회하는 것입니다.

#알고리즘

문제를 조금 일반화해 봅시다. 이제 우리는 구간 $[2, n]$의 각 수 $k$에 대해 소수인지 판별하는 것뿐만 아니라 그 수의 최소 소인수 $d_k$를 구하고자 합니다.

처음에는 배열 $d$를 0으로 채웁니다. 이는 모든 수가 소수라고 가정한다는 뜻입니다. 알고리즘이 진행되는 동안 이 배열은 점차 채워집니다. 이와 더불어, 현재까지 찾은 모든 소수의 목록 $p$를 유지하겠습니다.

이제 $k$를 $2$부터 $n$까지 차례로 살펴봅시다. 이 수가 소수이면, 즉 $d_k = 0$이면, $d_k = k$로 두고 $k$를 목록 $p$에 추가합니다.

다음으로, $k$의 소수 여부와 관계없이 배열 $d$에 값을 채워 넣는 과정을 시작합니다. 지금까지 찾은 소수 $p_i$ 가운데 $d_k$를 넘지 않는 것들을 순회하면서 $d_{p_i k} = p_i$로 대입합니다.

const int n = 1e6;

int d[n + 1];
vector<int> p;
 
for (int k = 2; k <= n; k++) {
    if (p[k] == 0) {
        d[k] = k;
        p.push_back(k);
    }
    for (int x : p) {
        if (x > d[k] || x * d[k] > n)
            break;
        d[k * x] = x;
    }
}

이 알고리즘은 각 수마다 비트 하나 대신 약수(int, 4바이트)를 저장해야 하므로 일반적인 체보다 최소 32배 많은 메모리를 필요로 합니다. 선형 체는 점근적 복잡도가 더 좋기는 하지만, 실제로는 속도 면에서도 최적화된 에라토스테네스의 체에 뒤처집니다.

#응용

배열 $d$를 사용하면 임의의 수 $k$의 소인수분해를 그 소인수분해의 크기에 비례하는 시간에 구할 수 있습니다.