쌍문동 척척박사
Spring / ReactJS / PS

에라토스테네스의 체 (소수)

에라토스테네스의 체 (소수)

BOJ 4948 베르트랑 공준를 풀어보자. 소수 문제를 처음 푸는 경우 다음 풀이가 가장 먼저 떠올랐을 거다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.io.*;
import java.util.*;

class Solution{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public Solution() throws IOException {
        while(true){
            int cnt = 0;
            int num = Integer.parseInt(br.readLine());
            if(num == 0)    break;

            for(int n = num+1, mod; n <= 2*num; n++){
                for(mod = 2; mod < n; mod++){
                   if(n % mod == 0) break;
                }
                cnt += n == mod ? 1 : 0;
            }
            System.out.println(cnt);
        }

    }
}

하지만 N이 조금만 커져도 바로 시간 초과가 난다. 실제로 위 알고리즘의 시간 복잡도는 O(N^2)이다. 따라서 우리는 다른 기법이 필요하다.

기본 개념

에라토스테네스의 체는 가장 유명한 소수 찾기 테크닉 중 하나로, 1~N 범위 내의 모든 소수를 찾을 때, 2부터 시작해 차례차례 나타나는 수들의 배수를 모두 소수가 아닌 수로 제외시키며 소수인지 여부를 미리 저장해두는 알고리즘이다. 자세한 내용은 다음 그림으로 확인하자. (출처: 위키백과)

2.gif

구현은 다음과 같으며, 시간 복잡도는 O(Nlg(lgN))이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.io.*;
import java.util.*;

class Solution{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    final int MAXN = 123456 + 1;

    boolean[] notPrime = new boolean[2*MAXN];

    public Solution() throws IOException {
        notPrime[0] = notPrime[1] = true;
        for(int i = 2; i < 2*MAXN; i++){
            if(notPrime[i]) continue;
            for(int m = i*2; m < 2*MAXN; m += i){
                notPrime[m] = true;
            }
        }
        while(true){
            int cnt = 0;
            int num = Integer.parseInt(br.readLine());
            if(num == 0)    break;

            for(int n = num+1; n <= 2*num; n++){
                cnt += !notPrime[n] ? 1 : 0;
            }
            System.out.println(cnt);
        }

    }
}

유클리드 호제법과 마찬가지로, 소수 자체의 문제 말고도 다른 유형 문제에서도 부분 문제로서 테크닉이 사용될 수 있으니 익혀두도록 하자.

추가 문제

comments powered by Disqus