소수를 구하는 효율적인 알고리즘에는 에라토스테네스의 체라는 것이 있습니다.
소수는 약수가 자기 자신과 1만 있는 숫자를 말하는데, 이것은 단순한 반복문으로도 구할 수는 있습니다.
숫자 한 개에 대해서 그것이 소수인가? 판별할 때에는 반복문으로 구해도 아주 큰 문제는 없을 것입니다.
하지만 다량의 소수를 한꺼번에 판별해서 구해야 할 경우에는 이야기가 달라집니다.
많은 숫자들에 대해 일일이 판별하다 보면 실행시간은 한없이 길어질 것입니다.
이 때 사용하는 알고리즘이 “에라토스테네스의 체(Sieve of Eratosthenes)” 입니다.
에라토스테네스의 체
마치 체처럼 걸러낸다고 하여 이름 붙인 이 알고리즘은, 2 이상 n 이하의 정수 x가 소수인지 아닌지 효율적으로 판단할 수 있도록 추가적인 배열을 만드는 전처리 알고리즘입니다.
여기서는 이 배열의 이름을 sieve라고 하겠으며, sieve[x] = 0 이면 소수이고, sieve[x] = 1이면 소수가 아니라는 의미로 정하겠습니다.
이 알고리즘의 개념은 깔끔합니다.
초기 sieve 배열의 모든 값은 0으로 초기화되어 있습니다.
- 2부터 차례대로 정수를 살펴 봅니다.
- 2가 소수입니다. 따라서, 2의 배수들은 sieve[x] = 1로 전부 표시해 놓습니다.
- 이럴 경우 sieve[4] = sieve[6] = sieve[8] = … = 1이 됩니다.
- 이제 다음 숫자를 살펴봅니다. (sieve[x] == 1인 x는 살펴보지 않고 반복문상에서 건너뛸 수 있습니다.)
- 3은 sieve[3] = 0 이었습니다. 따라서 소수이며, 3의 배수들은 전부 1로 표시해 놓습니다.
- 4를 봅니다. 4는 이미 sieve[4] = 1이므로 건너뜁니다.
- 5를 봅니다. sieve[5] = 0 이므로 소수이며, 5의 배수들은 전부 1로 표시해 놓습니다.
- …
이런 식으로 새로운 소수 x를 발견할 때마다, 그의 배수들을 모두 소수가 아니라고 표시해 놓습니다.
이렇게 하면 반복문 내에서 건너뛸 수 있는 숫자들이 많아져서, 숫자 하나하나마다 일일이 나누기 등을 해 가면서 소수인지 하나씩 판단하는 것보다 매우 빨라지게 됩니다.
1
2
3
4
5
6
7
for(int x = 2; x <= n; x++){
if(sieve[x] == 1) continue;
for (int u = 2*x; u<=n; u+=x){
sieve[u] = 1; // x가 소수였을 경우, 그 다음 큰 배수부터 전부 1로 표시해 놓기
// 예: x가 5였을 경우, 10부터 시작하여 15, 20, 25, ...를 전부 1로 표시
}
}
실제로 에라토스테네스의 체는 알고리즘 수행 시간이 O(nlog*log_n) 임을 보일 수 있는데, 이것은 O(n)에 매우 근접한 시간 복잡도라고 합니다.
- 위의 코드에서, 안에 있는 반복문은 x가 소수일 때만 수행되기 때문에 사실 알고리즘의 수행 상한보다 더 효율적이라고 할 수 있다.
에라토스테네스의 체 확장하기 : 빠른 소인수분해
이렇게 구해 놓은 sieve 배열에는 0과 1 값들이 각 숫자마다 들어가 있을 것입니다.
이를 이용하면, 소인수분해를 빠르게 할 수 있습니다.
소인수 분해라는 것이 소수들이 무엇인지 알아야 하기 때문에 이 특성을 이용해 금방 구할 수 있습니다!
1
2
3
4
5
6
7
8
9
// 소인수분해
for (int i = 0; n > 1; i++) {
if (sieve[i] == 0) { // i가 소수였을 경우,
while (n % i == 0) { //n이 그 소수로 나누어 떨어진다면?
printf("%d ", i); //그 소수를 출력하고
n /= i; //n을 그 소수로 나눈 후 다시 반복
}
}
}
단, 예외 처리를 하기 위해 sieve[0] 이나 sieve[1] 은 소수가 아니다(1) 로 미리 표시해 둡니다.
- 백준에서 소수 관련 문제 풀기
- 1929 : 소수 구하기 - https://www.acmicpc.net/problem/1929
- 1978 : 소수 찾기 - https://www.acmicpc.net/problem/1978
- 4948 : 베르트랑 공준 - https://www.acmicpc.net/problem/4948
- 3896 : 소수 사이 수열 - https://www.acmicpc.net/problem/3896
- 6588 : 골드바흐의 추측 - https://www.acmicpc.net/problem/6588