에라토스테네스의 체 (Sieve of Eratosthenes) - soo:bak
작성일 :
개념
에라토스테네스의 체, Sieve of Eratosthenes 는 고대 그리스의 수학자 에라토스테네스가 처음으로 제안한 소수 를 찾는 방법입니다.
이 알고리즘은 특정 범위 내의 모든 소수를 찾는데 사용되며, 효율성과 간결함으로 인해 여전히 널리 사용되고 있습니다.
시간 복잡도는 \(O(n \log \log n)\) 으로, 소수 판별 알고리즘 중에서 가장 빠른 편에 속합니다.
알고리즘의 원리가 간단하여 이해하기 쉽고, 코드로 구현하기도 비교적 간편합니다.
따라서, 소수 찾기 문제에 있어서 기본적인 알고리즘으로 사용되고는 합니다.
원리 및 설명
에라토스테네스의 체의 시작 : 수열 생성
에라토스테네스의 체 는 먼저 2 부터 n 까지의 모든 자연수의 수열을 생성하는 것으로 시작합니다.
이 수열은 소수 판별의 ‘검사’ 대상이 됩니다.
숫자 1 은 소수의 정의에 부합하지 않기 때문에, 2 부터 검사를 시작합니다.
소수 찾기 : 배수의 제거
가장 작은 수인 2 를 소수로 간주하고, 이 숫자의 모든 배수 를 소수가 아니라고 판별합니다.
왜냐하면, 소수 는 1 과 자기 자신 이외의 어떤 수로도 나누어 떨어지지 않는 수이므로,
2 를 제외한 2 의 배수는 소수가 될 수 없기 때문입니다.
반복 : 소수 찾기와 배수의 제거
이제, 소수가 아니라는 판별 과정을 거친 후 남아있는 수들 중에서 다음으로 가장 작은 수를 선택하고,
이 수를 소수로 간주합니다.
마찬가지로, 이 숫자의 모든 배수 를 소수가 아니라고 판별합니다.
이 과정은 현재 선택된 수의 제곱이 n보다 커지기 전까지 반복됩니다.
제곱근까지만 약수를 확인하면 되는 이유
어떤 수 \(n\)이 소수인지 아닌지를 판별하기 위해서는 \(n\)을 나눌 수 있는 약수가 존재하는지를 확인해야 합니다.
모든 수를 다 나눠보는 것은 비효율적이므로, 보다 빠른 판별을 위해 약수의 성질을 고려해야 합니다.
어떤 수 \(n\)이 두 수의 곱으로 나타낼 수 있다고 하면,
\(n = a \times b\)와 같은 관계가 성립합니다.
이때 \(a \leq b\)라고 가정하면,
\(a \leq \sqrt{n}\), \(b \geq \sqrt{n}\)이 항상 성립합니다.
그 이유는 다음과 같습니다 :
-
만약 두 수 모두 \(\sqrt{n}\)보다 작다면, 두 수의 곱은 \(n\)보다 작아집니다.
\(a < \sqrt{n}, \quad b < \sqrt{n} \Rightarrow a \times b < \sqrt{n} \times \sqrt{n} = n\)
-
반대로, 두 수 모두 \(\sqrt{n}\)보다 크다면, 곱은 \(n\)보다 커집니다.
\(a > \sqrt{n}, \quad b > \sqrt{n} \Rightarrow a \times b > \sqrt{n} \times \sqrt{n} = n\)
따라서 두 수 중 하나는 반드시 \(\sqrt{n}\)보다 작거나 같고, 다른 하나는 \(\sqrt{n}\)보다 크거나 같아야 합니다.
이로 인해 \(n\)의 약수는 항상 \(\sqrt{n}\)을 기준으로 쌍을 이루게 됩니다.
그러므로 \(\sqrt{n}\)까지만 확인하면 소수 여부를 판단하는 데 충분합니다.
이 과정은 \(n\)보다 큰 제곱수가 나오기 전까지 반복됩니다.
소수가 아닌 수는 반드시 두 수의 곱으로 표현되며,
이때 두 수는 하나가 \(\sqrt{n}\)보다 작거나 같고, 다른 하나는 크거나 같아야 합니다.
그렇지 않으면 곱의 결과가 \(n\)보다 작거나 커지게 됩니다.
이 논리에 따라 소수 판별 시에는 \(\sqrt{n}\)까지만 확인하면 충분합니다.
- 약수의 쌍 예시 (\(n = 36\))
| a | b | 관계 |
|---|---|---|
| 1 | 36 | a < \(\sqrt{36}\) |
| 2 | 18 | a < \(\sqrt{36}\) |
| 3 | 12 | a < \(\sqrt{36}\) |
| 4 | 9 | a < \(\sqrt{36}\) |
| 6 | 6 | a = \(\sqrt{36}\) |
\(\sqrt{36} = 6\)이므로, 6 이하의 값만 확인해도 모든 약수를 파악할 수 있습니다.
결과 : 소수의 추출
반복 과정이 끝나면, 남아 있는 모든 수들은 소수입니다.
남아있는 수들 각각은 앞선 과정에서 어떤 수의 배수로도 소수가 아니라고 표기되지 않았기 때문에,
이들 모두는 소수라고 간주할 수 있습니다.
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int n; // n 보다 작은 모든 소수를 찾는 예시
vector<bool> isPrime(n + 1, true); // 우선, 모든 수를 소수라고 가정
isPrime[0] = isPrime[1] = false; // 숫자 0과 1은 소수의 정의에 부합하지 않기 때문에 false 로 표기
for (int i = 2; i * i <= n; i++) { // 숫자 2부터 시작하여 n의 제곱근까지 범위 설정
if (isPrime[i]) { // 만약, 아직 소수라고 표기된 상태, 즉 초기 상태 혹은 검사가 되지 않은 수인 경우
for (int j = i * i; j <= n; j += i)
isPrime[j] = false; // 배수에 대해서 소수가 아니라고 표기
}
}
// 에라토스테네스의 체로 n 이하의 모든 자연수에 대한 소수 판별 완료.
for (int i = 0; i <= n; i++)
if (isPrime[i])
cout << i << "\n;" // n 이하의 자연수들 중 소수로 판별된 모든 수를 한 줄마다 출력