3. Eratosthenes' Sieve (에라토스테네스의 체)

소수 판별 알고리즘은 정말 많은데요.

그 중에서도 가장 많이 쓰이고 간편한 '에라토스테네스의 체'입니다.

어떤 수 N에 대하여, 소수 판별하는 코드를 만들때 가장 나이브한 방법은 2부터 N까지 하나씩 다 나눠 보는 방법이 있습니다.

소수판별.java(Naive)

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        System.out.println(isPrime(N) ? "소수": "소수가 아님");
    }
    
    private static boolean isPrime(int n) {
        for(int i = 2; i < n; i++) {
            if(n % i == 0) return false;
        }
        
        return true;
    }
}

작은 수의 경우 이정도는 가볍게 돌지만 N이 커지면 커질수록 시간 복잡도 또한 O(N)이므로 상당히 많은 시간이 걸립니다.

또한 N보다 작은 수에 존재하는 소수를 찾는다고 가정을 해보세요. 말도 안되게 느려지겠죠?

이때는 N의 값이 10000을 넘어가도 N^2만큼 돌아야 하므로 매우 비효율적이라는 것을 알 수 있습니다.

이를 위해서 적당한 범위 내에 존재하는 소수를 찾을 때 사용하는 것이 에라토스테네스의 체입니다.

수가 매우 커지면 좀 더 어렵고 복잡한 알고리즘으로 판별은 가능합니다.

그에 해당하는 밀러-라빈 소수 판별법에 대해 공부해봤었는데, 뭐가 뭔지 도통 모르겠고..

또 특정 문제가 아니라면 거의 쓰이지 않아서 따로 정리는 못할 것 같습니다.

그래서 오늘은 소수 판별 알고리즘 중 가장 많이쓰이는 에라토스테네스의 체만 알아보도록 할게요.ㅠㅠ

'체'라고 하면 다들 아시는 그 체입니다. 뭔가를 걸러낼 때 쓰는 그 '체'요.

즉, 이 알고리즘을 통해 특정 자연수 아래의 합성수는 모두 걸러내고 소수만 판별할 수 있습니다.

우선 코드부터 보고 어떻게 증명이되는지 시간복잡도는 어느정도인지 알아볼게요.

Eratosthenes' Sieve.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        System.out.println(isPrime(N));
    }
    
    private static StringBuilder isPrime(int n) {
        StringBuilder sb = new StringBuilder();
        
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        
        isPrime[0] = isPrime[1] = false;
        
        for(int i = 2; i <= n; i++) {
            if(!isPrime[i]) continue;
            
            for(int j = i + i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
        
        for(int i = 0; i < n; i++) {
            if(isPrime[i]) sb.append(i).append(" ");
        }
        
        return sb;
    }
}

알고리즘의 핵심적인 부분은 21~27번째 줄입니다.

사람들마다 코드 짜는 방식이 다르기 때문에 코드를 외우기보단 이해하고 자신이 편한 방법으로 맞춰 쓰시는게 좋을 것 같습니다.

우선 isPrime 배열은 해당 배열의 인덱스 값이 소수에 해당하면, 해당 배열은 true의 값을 가집니다.

그렇기 때문에 맨 처음 값을 모두 참으로 바꿔주고, 반복문을 돌리면서, 소수가 아닌 합성수를 모두 false로 바꾸는 작동을 합니다.

간단하게도 한계점이 보이죠? 맞습니다. 배열 사이즈보다 큰 숫자 범위는 이 방법으로 구할 순 없습니다.

(물론 좀 더 큰 소수를 정수 배열의 값으로 저장하시면 이보단 많이 구해 낼 수 있습니다.)

어쨌든 이렇게 하고 N에 100을 넣으면 아래와 같이 결과가 나옵니다.

출력 결과

결과는 잘 나오는데, 과연 숫자가 커져도 정확히 합성수를 걸러 낼 수 있는 것인지, 그리고 얼마나 빠른지가 궁금하실 겁니다.

우선 이 알고리즘이 정확한 것인지부터 알아볼게요.

증명

j의 값에 따라 합성수가 걸러지는 것은 코드만 봐도 알 수 있습니다.

이를 확인해보면..

i가 짝수인 경우

j = i * 2의 값으로 시작하고 j += i로 값이 증가합니다. 따라서 i가 짝수인 경우 j는 무조건 4보다 큰 짝수입니다.

짝수인 경우 2는 소수지만 4보단 작기 때문에 상관 없죠.

확실히 이 경우에선 소수는 걸러지지 않겠습니다. 그럼 이제 모든 짝수가 걸러지는지만 보면 되겠네요.

i = 2의 경우

j = 4, 6, 8, 10, .... , 2 * N

이미 i가 2 일때 N까지 모든 짝수가 모두 걸러집니다.

i가 홀수인 경우

이때는 우선 i는 홀수지만, j는 짝수로 시작이 됩니다. (j = i + i 즉, i * 2이므로)

i는 그리고 홀수라는 가정하에 3이상의 홀수입니다. 여기서도 과연 나머지 합성수가 걸러지고 소수는 유지될까요?

i = 3의 경우

j = 6, 9, 12, 15, 18, .... 3 * N

i = 5의 경우

j = 10, 15, 20, 25, ....  5 * N

일반화: i = k의 경우 (단, k는 홀수)

j = (2 * k), (3 * k), (4 * k), .... (N * k)

일반화 한 경우 현재 걸러지는 숫자들은 어떤 홀수 k의 배수이므로, 합성수이니 다른 소수는 건들지 않는다는게 확실하네요.

그리고 사실 짝수도 여러 i의 경우를 써보시면 알겠지만, 시작수 i의 배수를 걸러내는 식으로 작동됩니다.

또한 기본적으로 i + i를 통해 어떤수 i의 2배부터 탐색해 나가기 때문에 소수인 i는 절대 걸러내지 못합니다.

즉 정리해보면,

1. (j = i + i)와 (j += i)를 통해 어떤 수 i에 대한 배수가 모두 걸러진다. (어떤 수 N보다 작은 i의 배수)
2. 또한, (j = i + i)이므로, i라는 수가 소수인 경우엔 i가 자동으로 배제된다.
3. N이하의 모든 수를 통해 계속 그 배수를 걸러나가므로 N이하의 합성수는 모두 제거된다.

정도 되겠습니다.

이 알고리즘으로 확실하게, 모든 수를 걸러 낼 수 있다는 것은 이해하셨으리라 믿습니다.

근데 사실은 바깥 반복문은 N까지 돌릴 필요 없이, N^(1/2)까지만 돌려도 됩니다. (실제로도 그렇게 쓰이구요.)

우선 제가 이해한대로 설명드려보면,

N^(1/2)까지 돌린다는 말은, 결국 N^(1/2)이하의 수에 의해 N^(1/2)값 이후의 모든 N의 약수인 합성수가 걸러진다는 의미입니다.

그러면 우린 그게 과연 가능한지만 알아보면 되겠네요.

1. 당연하게도 N^(1/2)보다 큰 수인지 아닌지 상관없이 소수는 여전히 걸러지지 않습니다.
2. 또한 N^(1/2)보다 큰 수에서 합성수는 N보다는 작습니다.
3. 따라서 아까 위에서 본 방식과 같이 N이 N^(1/2)보다 작은 값을 약수(i)로 가진다면, 모두 걸러 낼 수 있겠네요.
4. 그 중 짝수는 무조건 2의 배수니까 짝수는 다 걸러집니다.
5. 나머지 홀수 중 합성수는 어떨까요? 귀류법으로 생각해볼게요.
6. 1을 제외한 모든 약수를 N^(1/2)보다 큰 수로 가지는 수 N이 존재한다.라는 명제를 생각해 볼게요.
7. 6의 명제가 거짓이면 결국 N은 적어도 1개의 약수를 N^(1/2)보다 작은 범위에서 가진다는 말이됩니다.
8. 그리고 그 범위에서 약수를 가진다면 N^(1/2)보다 큰 합성수는 우리가 구한 약수로 제외시킬 수 있으니 충분히 걸러지겠죠.

6번 명제 증명

예를 들어 어떤 수 N = a * b (단, a > b 그리고 b != 1) 라고 가정해 보겠습니다.

N이 제곱수가 아니라면 b < N^(1/2) < a 이러한 조건이 성립하죠. 왜냐하면 모든 약수들은 어떤 수 N의 제곱근에 의해 양분 되니까요.

이렇게 봤을때 이미 N^(1/2)보다 작은 약수가 존재하네요. (이때 b가 1이라면 a = N이고, 이 수는 소수가 됩니다.)

6번 명제는 거짓이므로, N^(1/2) 보다 큰 합성수는 N^(1/2) 이하의 수에서 적어도 하나를 약수로 가집니다.

사실.. 저는 감으로 이해했기 때문에, wiki에서 자세한 내용을 보시면 좋을 것 같습니다.

에라토스테네스의 체 시간복잡도는 O(nlog(logn)) 입니다.

바깥 반복문 logn, 내부 반복문 logn 인데, 가장 앞의 n은 어떻게 해석할 수 있을지 모르겠네요...

감으로는 느껴지지만 증명 자체는 이해가 잘 안가고 그래서인지 설명드리기도 어려울 것 같습니다.ㅜㅜ

해당 내용도 위의 위키백과 링크를 참고해주세요..ㅠ (죄송합니다..)

질문이나 틀린 부분 있으면 댓글 달아주세요!

빠르게 답변이나 보완하도록 하겠습니다. 감사합니다.