에라토스테네스의 체란
"In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit."
(번역) 수학에서, 에라토스테네스의 체는 주어진 한계까지의 모든 소수를 찾는 고대 알고리즘이다.
소수를 체로 걸러낸다고 하여 이렇게 이름이 지어졌다. 핵심 아이디어는 하나다.
소수의 배수들을 목록에서 지워나간다.
여러 개의 소수를 판별하기 위해서는 **동적 계획법(Dynamic Programming)**을 활용해야 한다. 크기가
N N N 인 배열에 해당 인덱스의 수가 소수인지의 여부를 저장해 둔다면 특정 범위에 대한 소수 목록을 효율적으로 구할 수 있다.
O ( N ) O(\sqrt{N}) O ( N ) 일반적으로 입력받은 수가 소수인지를 판단하는 코드는
O ( N ) O(\sqrt{N}) O ( N ) 의 알고리즘을 사용할 수 있다.
bool is_prime (int n) if (n < 2 ) return false ;
for (int i = 2 ; i * i <= n; i++) {
if (n % i == 0 ) return false ;
}
return true ;
}
2 2 2 부터
n \sqrt{n} n 까지 나누어떨어지는지에 따라 주어진 수가 소수인지 판별하는 함수이다. 가장 효율적인 알고리즘은 아니지만 구현하기도 쉽고 시간복잡도도 나름 나쁘지 않기 때문이다.
하지만 여러 개의 수에 대한 소수 판별을 위 방법대로 한다면 매우 비효율적일 것이다.
1 1 1 부터
N N N 까지 위 방식대로 소수의 개수를 센다면 다음과 같은 코드가 구현될 것이다.
int cnt = 0 ;
for (int i = 1 ; i <= n; i++) {
if (is_prime (i)) ++cnt;
}
O ( N ) O(\sqrt{N}) O ( N ) 의 알고리즘을
N N N 번 적용하므로 최종적인 시간복잡도는
O ( N N ) O(N\sqrt{N}) O ( N N ) 이 된다. 보통 1억번의 연산을 1초로 가정하므로,
N N N 이 20만을 넘어가면 이 방법은 사용하기에 매우 느린 알고리즘이 된다.
구현
bool seive[N + 1 ];
std::fill (seive+ 2 , seive + N + 1 , true );
for (int i = 2 ; i * i <= N; i++) {
if (!seive[i]) continue ;
for (int j = i * i; j <= N; j += i) seive[j] = false ;
}
에라토스테네스의 체의 핵심은 소수의 배수를 차례로 지워나간다는 것이다. seive배열은 해당 인덱스의 수가 소수인지를 담고 있는 배열이다. 예를 들어 seive[2] == true이면 2는 소수, seive[4] == false이면 4는 합성수이다.
처음에는 배열의 모든 인덱스에 대하여 true를 할당한다.
bool seive[N + 1 ];
std::fill (seive + 2 , seive + N + 1 , true );
첫 번째 반복문은
2 2 2 부터
N \sqrt{N} N 까지의 수에 대해서만 검사한다.
for (int i = 2 ; i * i <= N; i++) {
...
}
N \sqrt{N} N 보다 큰 수의 배수들은 이미 이전 단계에서 모두 처리되므로 검사할 필요가 없다.
현재 숫자 i가 이미 소수가 아니라고 판별되었다면 건너뛴다.
이는 i가 이전 단계에서 처리된 어떤 소수의 배수였다는 의미이다.
현재 소수 i의 배수들을 모두 소수가 아니라고 표시한다.
for (int j = i * i; j <= N; j += i) seive[j] = false ;
j가
i * i부터 시작하는 이유는 (
i * 2,
i * 3, ...,
i * (i - 1))은 이미 처리되었기 때문이다.
i씩 증가시키면서
N N N 까지의 모든
i의 배수를 판별한다.
시간복잡도: O ( N log log N ) O(N \log \log N) O ( N log log N )
일단 결론부터 말하면 에라토스테네스의 체의 시간복잡도는
O ( N log log N ) O(N \log \log N) O ( N log log N ) 이다.
1 , . . . , N 1,\;...,\;N 1 , ... , N 까지의 수를 처리한다는 점에서
O ( N ) O(N) O ( N ) 은 쉽게 납득할 수 있다. 무엇인가
O ( log log N ) O(\log \log N) O ( log log N ) 의 시간이 걸린다는 것이다.
아래 증명 과정은 엄밀한 증명이 아니니 개괄적인 흐름만 파악해주시길 바랍니다.
에라토스테네스의 체의 알고리즘을 생각해보자.
2 2 2 4 , 6 , 8 , . . . 4, 6, 8, ... 4 , 6 , 8 , ... N 2 \frac{N}{2} 2 N 3 3 3 6 , 9 , 12 , . . . 6, 9, 12, ... 6 , 9 , 12 , ... N 3 \frac{N}{3} 3 N 5 5 5 10 , 15 , 20 , . . . 10, 15, 20, ... 10 , 15 , 20 , ... N 5 \frac{N}{5} 5 N 7 7 7 14 , 21 , 28 , . . . 14, 21, 28, ... 14 , 21 , 28 , ... N 7 \frac{N}{7} 7 N ⋮ \vdots ⋮
각 소수에 대하여
N N N 이하의 배수들을 제거하므로 소수
p p p 에 대하여 약
N p \frac{N}{p} p N 개의 제거 연산을 한다.
N \sqrt{N} N 이하의 소수가
k k k 개 있다고 할 때, 총 연산 횟수는 아래와 같다:
N ( 1 2 + 1 3 + 1 5 + ⋯ + 1 p k ) = N ∑ p ∈ P p ≤ N 1 p N\left(\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \cdots + \frac{1}{p_k}\right) = N \sum_{p \in \mathbb{P}}^{p \leq N} \frac{1}{p} N ( 2 1 + 3 1 + 5 1 + ⋯ + p k 1 ) = N p ∈ P ∑ p ≤ N p 1 즉, 소수의 역수의 합인
∑ p ∈ P p ≤ N 1 p \sum_{p \in \mathbb{P}}^{p \leq N} \frac{1}{p} ∑ p ∈ P p ≤ N p 1 가
log log N \log \log N log log N 으로 근사됨을 보이는 것이 핵심이다.
조화급수와 오일러 곱
**조화급수(Harmonic Series)**를 생각해보자. 조화급수란 각 항의 역수가 등차수열을 이루는 급수이다.
∑ n = 1 ∞ 1 n = 1 + 1 2 + 1 3 + 1 4 + ⋯ \sum_{n = 1}^{\infty} \frac{1}{n} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots n = 1 ∑ ∞ n 1 = 1 + 2 1 + 3 1 + 4 1 + ⋯ 조화급수는 보이는 것과 다르게 소수와 밀접하게 연관되어 있다. 조화급수를 소수에 대한 식으로 표현하면:
∑ n = 1 ∞ 1 n = ∏ p ∈ P ( 1 + 1 p + 1 p 2 + ⋯ ) = ∏ p ∈ P 1 1 − p − 1 \sum_{n = 1}^{\infty} \frac{1}{n}
= \prod_{p \in \mathbb{P}} \left(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots\right)
= \prod_{p \in \mathbb{P}} \frac{1}{1 - p^{-1}} n = 1 ∑ ∞ n 1 = p ∈ P ∏ ( 1 + p 1 + p 2 1 + ⋯ ) = p ∈ P ∏ 1 − p − 1 1 급수가 갑자기 왜 누승(누적곱)이 되는지 직관적인 이해가 힘들 수 있다. 이해를 돕기 위하여 누승을 전개하면 아래와 같다:
∏ p ∈ P ( 1 + 1 p + 1 p 2 + ⋯ ) = ( 1 + 1 2 + 1 2 2 + 1 2 3 + ⋯ ) = ( 1 + 1 3 + 1 3 2 + 1 3 3 + ⋯ ) = ( 1 + 1 5 + 1 5 2 + 1 5 3 + ⋯ ) = ( 1 + 1 7 + 1 7 2 + 1 7 3 + ⋯ ) = ( 1 + 1 7 + 1 7 2 ) ⋮ \begin{aligned}
\prod_{p \in \mathbb{P}} \left(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots\right) =
&\left(1 + \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \cdots\right) \\
= &\left(1 + \frac{1}{3} + \frac{1}{3^2} + \frac{1}{3^3} + \cdots\right) \\
= &\left(1 + \frac{1}{5} + \frac{1}{5^2} + \frac{1}{5^3} + \cdots\right) \\
= &\left(1 + \frac{1}{7} + \frac{1}{7^2} + \frac{1}{7^3} + \cdots\right) \\
=&\phantom{\left(1 + \frac{1}{7} + \frac{1}{7^2}\right)} \vdots
\end{aligned} p ∈ P ∏ ( 1 + p 1 + p 2 1 + ⋯ ) = = = = = ( 1 + 2 1 + 2 2 1 + 2 3 1 + ⋯ ) ( 1 + 3 1 + 3 2 1 + 3 3 1 + ⋯ ) ( 1 + 5 1 + 5 2 1 + 5 3 1 + ⋯ ) ( 1 + 7 1 + 7 2 1 + 7 3 1 + ⋯ ) ( 1 + 7 1 + 7 2 1 ) ⋮ 이때 임의의 수를 떠올려보자. 예를 들어 그 수가
42 42 42 이고, 소인수분해를 하면
42 = 2 × 3 × 7 42 = 2 \times 3 \times 7 42 = 2 × 3 × 7 이다. 조화급수의 항
1 42 = 1 2 × 1 3 × 1 7 \frac{1}{42} = \frac{1}{2} \times \frac{1}{3} \times \frac{1}{7} 42 1 = 2 1 × 3 1 × 7 1 으로 유일하게 표현되고 그 외의 방법은 없다. 누승에서 각 항의 소수의 거듭제곱에 대한 역수를 적절히 선택하면 모든 자연수를 만들 수 있다. 모든 자연수는 유일한 소인수분해 결과를 가지기 때문이다.
소수의 역수의 합이 log log N \log \log N log log N
∑ n = 1 ∞ 1 n = ∏ p ∈ P 1 1 − p − 1 \sum_{n = 1}^{\infty} \frac{1}{n} = \prod_{p \in \mathbb{P}} \frac{1}{1 - p^{-1}} n = 1 ∑ ∞ n 1 = p ∈ P ∏ 1 − p − 1 1 위 식이 성립함을 보였으니, 양 변에 자연로그를 씌우면:
ln ∑ n = 1 ∞ 1 n = ln ( ∏ p ∈ P 1 1 − p − 1 ) = ∑ p ∈ P ln ( 1 1 − p − 1 ) = ∑ p ∈ P − ln ( 1 − p − 1 ) \begin{align}
\ln \sum_{n = 1}^{\infty} \frac{1}{n}
= \ln \left(\prod_{p \in \mathbb{P}} \frac{1}{1 - p^{-1}}\right)
= \sum_{p \in \mathbb{P}} \ln \left(\frac{1}{1 - p^{-1}}\right)
= \sum_{p \in \mathbb{P}} -\ln\left(1 - p^{-1}\right)
\end{align} ln n = 1 ∑ ∞ n 1 = ln p ∈ P ∏ 1 − p − 1 1 = p ∈ P ∑ ln ( 1 − p − 1 1 ) = p ∈ P ∑ − ln ( 1 − p − 1 ) 여기서
ln ( 1 − x ) \ln(1 - x) ln ( 1 − x ) 의 테일러 급수를 활용한다.
ln ( 1 − x ) = − ∑ n = 1 ∞ x n n = − x − 1 2 x 2 − 1 3 x 3 − 1 4 x 4 − ⋯ , ( ∣ x ∣ < 1 ) \ln(1 - x) = -\sum_{n = 1}^{\infty} \frac{x^n}{n} = -x - \frac{1}{2}x^2 - \frac{1}{3}x^3 - \frac{1}{4}x^4 - \cdots, \;(|x| < 1) ln ( 1 − x ) = − n = 1 ∑ ∞ n x n = − x − 2 1 x 2 − 3 1 x 3 − 4 1 x 4 − ⋯ , ( ∣ x ∣ < 1 ) ∣ 1 p ∣ < 1 \left|\frac{1}{p}\right| < 1 p 1 < 1 이므로,
− ln ( 1 − p − 1 ) = − ( − 1 p − 1 2 p 2 − 1 3 p 3 − 1 4 p 4 − ⋯ ) = 1 p + 1 2 p 2 + 1 3 p 3 + 1 4 p 4 + ⋯ \begin{aligned}
-\ln(1 - p^{-1})
&= -\left(-\frac{1}{p} - \frac{1}{2p^2} - \frac{1}{3p^3} - \frac{1}{4p^4} - \cdots\right) \\
&= \frac{1}{p} + \frac{1}{2p^2} + \frac{1}{3p^3} + \frac{1}{4p^4} + \cdots
\end{aligned} − ln ( 1 − p − 1 ) = − ( − p 1 − 2 p 2 1 − 3 p 3 1 − 4 p 4 1 − ⋯ ) = p 1 + 2 p 2 1 + 3 p 3 1 + 4 p 4 1 + ⋯ ln ∑ n = 1 ∞ 1 n = ∑ p ∈ P − ln ( 1 − p − 1 ) = ∑ p ∈ P ( 1 p + 1 2 p 2 + 1 3 p 3 + 1 4 p 4 + ⋯ ) = ∑ p ∈ P 1 p + ∑ p ∈ P 1 p 2 ( 1 2 + 1 3 p + 1 4 p 2 + ⋯ ) < ∑ p ∈ P 1 p + ∑ p ∈ P 1 p 2 ( 1 + 1 p + 1 p 2 + ⋯ ) = ∑ p ∈ P 1 p + ∑ p ∈ P 1 p ( p − 1 ) = ∑ p ∈ P 1 p + C \begin{align}
\ln \sum_{n = 1}^{\infty} \frac{1}{n}
&= \sum_{p \in \mathbb{P}} -\ln\left(1 - p^{-1}\right) \notag \\
&= \sum_{p \in \mathbb{P}} \left(\frac{1}{p} + \frac{1}{2p^2} + \frac{1}{3p^3} + \frac{1}{4p^4} + \cdots\right) \notag \\
&= \sum_{p \in \mathbb{P}} \frac{1}{p} + \sum_{p \in \mathbb{P}} \frac{1}{p^2}\left(\frac{1}{2} + \frac{1}{3p} + \frac{1}{4p^2} + \cdots\right) \notag \\
&< \sum_{p \in \mathbb{P}} \frac{1}{p} + \sum_{p \in \mathbb{P}} \frac{1}{p^2}\left(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots\right)
= \sum_{p \in \mathbb{P}} \frac{1}{p} + \sum_{p \in \mathbb{P}} \frac{1}{p(p - 1)} \notag \\
&= \sum_{p \in \mathbb{P}} \frac{1}{p} + C
\end{align} ln n = 1 ∑ ∞ n 1 = p ∈ P ∑ − ln ( 1 − p − 1 ) = p ∈ P ∑ ( p 1 + 2 p 2 1 + 3 p 3 1 + 4 p 4 1 + ⋯ ) = p ∈ P ∑ p 1 + p ∈ P ∑ p 2 1 ( 2 1 + 3 p 1 + 4 p 2 1 + ⋯ ) < p ∈ P ∑ p 1 + p ∈ P ∑ p 2 1 ( 1 + p 1 + p 2 1 + ⋯ ) = p ∈ P ∑ p 1 + p ∈ P ∑ p ( p − 1 ) 1 = p ∈ P ∑ p 1 + C ∑ p ∈ P 1 p ( p − 1 ) < ∑ n = 2 ∞ 1 n ( n − 1 ) = ∑ n = 2 ∞ ( 1 n − 1 − 1 n ) = 1 − 1 2 + 1 2 − 1 3 + ⋯ = 1 \sum_{p \in \mathbb{P}} \frac{1}{p(p - 1)} < \sum_{n = 2}^{\infty} \frac{1}{n(n - 1)}
= \sum_{n = 2}^{\infty} \left(\frac{1}{n - 1} - \frac{1}{n}\right)
= 1 - \frac{1}{2} + \frac{1}{2} - \frac{1}{3} + \cdots = 1 p ∈ P ∑ p ( p − 1 ) 1 < n = 2 ∑ ∞ n ( n − 1 ) 1 = n = 2 ∑ ∞ ( n − 1 1 − n 1 ) = 1 − 2 1 + 2 1 − 3 1 + ⋯ = 1 ( 2 ) (2) ( 2 ) 식으로부터 아래 식이 성립함을 보였다:
ln ∑ n = 1 ∞ 1 n < ∑ p ∈ P 1 p + C \ln \sum_{n = 1}^{\infty} \frac{1}{n} < \sum_{p \in \mathbb{P}} \frac{1}{p} + C ln n = 1 ∑ ∞ n 1 < p ∈ P ∑ p 1 + C 이때,
∫ 1 ∞ 1 x d x = lim x → ∞ ( ln ( x ) − ln ( 1 ) ) < lim x → ∞ ln ( x ) < ∑ n = 1 ∞ 1 n \int_1^{\infty} \frac{1}{x}dx = \lim_{x \to \infty} (\ln(x) - \ln(1)) < \lim_{x \to \infty} \ln(x) < \sum_{n = 1}^{\infty} \frac{1}{n} ∫ 1 ∞ x 1 d x = x → ∞ lim ( ln ( x ) − ln ( 1 )) < x → ∞ lim ln ( x ) < n = 1 ∑ ∞ n 1 이므로, 아래 식이 성립한다:
lim x → ∞ ln ln ( x ) < ln ∑ n = 1 ∞ 1 n < ∑ p ∈ P 1 p \begin{align}
\lim_{x \to \infty} \ln\ln(x) < \ln \sum_{n = 1}^{\infty} \frac{1}{n} < \sum_{p \in \mathbb{P}} \frac{1}{p}
\end{align} x → ∞ lim ln ln ( x ) < ln n = 1 ∑ ∞ n 1 < p ∈ P ∑ p 1 따라서 소수의 역수의 합이 발산하는 속도가
log log N \log \log N log log N 에 근접함을 알 수 있다. 이때 에라토스테네스의 체에서는
1 1 1 부터
N N N 까지
N N N 번 판별하므로 최종적인 시간복잡도는
O ( N log log N ) O(N \log \log N) O ( N log log N ) 이다.
참고
