소수를 구하는 방법은 여러가지가 있다. 하지만 시간이 덜 거리고 빠르게 찾을 수 있는 방법이 있다면 사람들은 그 방법을 사용하지 않을까? 맞다. 사람들은 짧은 시간이 걸리는 것을 선호한다. 세상의 공짜란 없듯이 짧은 시간이 걸리는 방법은 구현 방법이 기존보다는 조금 어렵다. 그렇다면 어떤 방법인지 알아보자.

소수란?

1과 자기 자신으로만 나누어 떨어지는 수를 소수라고 한다. 즉, 자기 자신보다 작은 수들로 나누어봐서 하나라도 나누어 떨어지는 수가 존재하면 소수가 아니라는 뜻이다.

에라토스테네스의 체

소수의 개념을 간단하게 알아봤으니 에라토스테네스의 체 방법을 알아보자.

  • 120까지의 모든 소수를 구한다고 가정해보자.
  • 2부터 120까지 수를 배열에 모두 넣는다.
  • 소수가 아닌 수들을 모두 체크해버린다.

2를 제외한 모든 2의 배수를 체크한다.
3을 제외한 모든 3의 배수를 체크한다.
4를 제외한 모든 4의 배수를 체크한다.

이와 같은 방식으로 소수가 아닌 수들을 체크한다. 그러면 배열에서 체크되지 않은 수들은 소수만 남게 된다. 생각보다 그렇게 어렵지 않고 간단하게 이해하고 구현할 수 있다.

# 첫 번째 방법

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
31
32
33
34
public class Main {
    private static final String NEW_LINE = "\n";
    private static final String SPACE = " ";

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(SPACE);
        int m = Integer.parseInt(input[0]);
        int n = Integer.parseInt(input[1]);

        int[] arr = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= n; j ++) {
                // 자신과 같지 않고 0으로 나누어 떨어지면 소수가 아니다. 
                if(arr[j] !=i && arr[j] % i == 0){
                    arr[j] = 0; // 소수가 아닌 경우 0을 넣는다. 
                }
            }
        }

        for (int i = m; i <= n; i++) {
            if (arr[i] != 0) {
                bw.write(i + NEW_LINE);
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

위의 방식으로 구하면 에라토스테네스의 체 방식을 이용하지 않는 방식보다 시간이 오래 걸린다. 그러면 우리가 이 방식을 사용하는 의미가 없지 않는가?? 이제 에라토스테네스의 체를 이용해 최상의 소수 구하기 프로그램을 만들어보자.

# 두 번째 방법

체크할 때 모든 수를 다 돌면서 체크할 필요 없이 체크할 배수만큼만 반복문을 돌게 하는 것이다. 그리고 이미 0으로 체크되어버린 수의 배수는 확인하지 않는다. 왜냐하면 어떤 수가 소수가 아니라면 그 수의 배수도 소수가 아니기 때문이다.

ex)
2를 제외한 2의 배수를 체크한다.
2,4,6,8,10,12,14 …

4를 제외한 4의 배수를 체크한다.
4,6,8,12,16,…
이미 2의 배수를 체크할 때 체크가 되어 있기 때문에 건너뛸 수 있다.

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
31
32
33
34
35
36
37
38
39
40
41
public class Main {
    private static final String NEW_LINE = "\n";
    private static final String SPACE = " ";

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(SPACE);
        int m = Integer.parseInt(input[0]);
        int n = Integer.parseInt(input[1]);

        boolean[] check = new boolean[n + 1];
        // 에라토스테네스의 체에서 0과 1은 제외하고 시작하기 때문에 체크한다.
        check[0] = check[1] = true;

        for (int i = 2; i <= n; i++) {
            // 체크되어 있으면 건너뛴다.
            // 체크가 되어 있다는 뜻은 소수가 아니라는 뜻이다.
            if (check[i]) {
                continue;
            }
            
            // 해당 수의 배수만큼 반복문을 돌면서 체크한다. 
            for (int j = i + i; j <= n; j += i) {
                // 소수가 아닌 것들을 true로 체크한다.
                check[j] = true;
            }
        }

        for (int i = m; i <= n; i++) {
            if (!check[i]) {
                bw.write(i + NEW_LINE);
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

이 경우 결과는 매우 짧은 시간이 나오는 것을 확인할 수 있었다. 앞으로 소수를 구할 때는 에라토스테네스의 체 방식을 이용하자.

참고