🛠 에라토스테네스의 체란?
고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.
단일 숫자 소수 여부 확인
어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.
수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다.
만약, 대량의 소수를 한꺼번에 판별해야할 경우는 에라토스테네스의 체를 사용하면 보다 빠르게 소수를 판별할 수 있다.
에라토스테네스의 체 원리
임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고 빠른 방법이다. 예를 들어 1~100까지 숫자 중 소수를 찾는다 하자.
일단 1부터 100까지 숫자를 쭉 쓴다.
일단 소수도, 합성수도 아닌 유일한 자연수 1을 제거하자.
2를 제외한 2의 배수를 제거한다.
3을 제외한 3의 배수를 제거한다.
4의 배수는 지울 필요 없다.(2의 배수에서 이미 지워졌다.) 그러면 2, 3 다음으로 남아있는 가장 작은 소수, 즉 5를 제외한 5의 배수를 제거해야 한다.
그리고 마지막으로 7을 제외한 7의 배수까지 제거하면 결과는 이렇다.
8의 배수는 지울 필요 없다.(2의 배수에서 이미 지워졌다.) 9의 배수도 지울 필요 없다.(3의 배수에서 이미 지워졌다.) 10의 배수도 지울 필요 없다.(2의 배수에서 이미 지워졌다.) 그리고 11 이상의 소수들의 배수부터는
11 > √100
이런 식으로 남은 것들의 2배수, 3배수,...n배수를 지우다보면 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 남는다. 이것이 100 이하의 소수이다.
이런 방법으로 만약 n이하의 소수를 모두 찾고 싶다면 1부터 n까지 쭉 나열한 다음에(...) 2의 배수, 3의 배수, 5의 배수...쭉쭉 나누는 것이다.
일종의 노가다 방식이라 상당히 무식한 방법이긴 하지만, 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우 아직까지 소수들 간의 연관성(=소수를 생성할 수 있는 공식)이 나오지 않았으므로 에라토스테네스의 체보다 빠른 방법이 없다.
다만 에라토스테네스의 체는 '특정 범위 내의 소수'를 판정하는 데에만 효율적이다. 만약 주어진 수 하나가 소수인가? 만을 따지는 상황이라면 이는 소수판정법이라 해서 에라토스테네스의 체 따위와는 비교도 안되게 빠른방법이 넘쳐난다.
에라토스테네스의 체 원리를 간단하게 설명하면
- 배열을 생성하여 초기화를 해준다.
- 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
- 2부터 시작하여 남아있는 수를 모두 출력한다.
<위키 백과사전>
✔ 에라토스테네스의 체 구현하기
import java.util.Arrays;
public class PrimeSieve {
public static final int MAX = 1000001;
public static boolean[] prime = new boolean[MAX];
public static void eratosthenes() {
// 배열을 false로 초기화합니다.
Arrays.fill(prime, false);
// 2와 3은 소수입니다. 따라서 5 이상의 홀수만 판별하면 됩니다.
prime[2] = true;
prime[3] = true;
// 5 mod 6과 1 mod 6을 참으로 설정합니다.
// 이들은 2의 배수도 아니고 3의 배수도 아닌 숫자 집합입니다.
// 단, 1은 소수가 아니므로 1 mod 6은 7부터 시작합니다.
for (int i = 5; i < MAX; i += 6)
prime[i] = true;
for (int i = 7; i < MAX; i += 6)
prime[i] = true;
for (int i = 5, j = 25, flag = 0; j < MAX;) {
int addi = 2 * (flag + 1);
// 현재 i가 소수인 경우
if (prime[i]) {
// i를 2배로 하여 i의 짝수곱을 굳이 검색하지 않게 합니다.
for (i *= 6; j < MAX; j += i) {
prime[j] = false;
}
i /= 6; // i 원상복구
j += addi * i;
for (i *= 6; j < MAX; j += i) {
prime[j] = false;
}
i /= 6; // i 원상복구
}
// 다음 루프를 위해 i를 조정합니다.
// 현재의 i가 5 mod 6이면 2를, 1 mod 6이면 4를 더합니다.
i += (flag == 0 ? 2 : 4);
j = i * i;
flag ^= 1;
}
}
}
📌참고
[1] 나무위키 https://namu.wiki/w/에라토스테네스의%20체
[2] 위키백과사전 https://ko.wikipedia.org/wiki/에라토스테네스의_체
[3] https://blog.naver.com/ndb796/221233595886
[4] https://velog.io/@max9106/Algorithm-에라토스테네스의-체
