문제 번호 1929번 : 소수 구하기(에라토스테네스의 체) - JAVA [자바]

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

문제 설명

 

주어진 수의 사이에 있는 소수를 구하는 문제입니다.

 

문제 풀이

정말 오래 걸리고 골치 아팠던 문제입니다. 소수 구하는 공식은 사실 어렵지 않은데 계속 속도 이슈가 걸리는 문제가 있었습니다. 여기서 에라토스테네스의 체 알고리즘을 사용해서 풀면 속도 이슈가 해결되지만 이 알고리즘을 이해하기까지 오랜 시간이 걸렸습니다. 최대한 저의 수준에서 이해할 수 있도록 코드를 해석하고 설명해 놓았으니 도움이 되었으면 좋겠습니다.

 

import java.util.Scanner;

public class Main {
    public static boolean[] primBool;//해당 index가 소수인지 합성수인지 판별하는 배열
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();

        prime_check(n);

        for(int i=m; i<primBool.length; i++){
            if(primBool[i] == false){
                System.out.println(i);
            }
        }
    }

    //배열에 index가 소수이면 false 아니면 true를 부여
    public static void prime_check(int n){
        /*
        에라토스테네스의 체 알고리즘
        기본적으로 배열이 모두 처음에 false이기 때문에 모두 소수라는 가정한다.
        소수의 반대는 합성수이다. 이 알고리즘은 합성수를 모두 걸러내는 형식으로 소수를 판별하는 알고리즘이다.
        합성수는 소수로 이루어진 곱이다. 예를 들어 2*2=4, 3*2*2=12 등등 모두 소수의 곱으로 표현할 수 있다.
        합성수의 또 특징은 가장 작은 소수의 배로 표현할 수 있다는 것이다. 12는 2*2*3으로 표현할 수 있지만 2의 6배로 표현할 수 있다.
        9는 3의 3배로 표현할 수 있다. 이처럼 소수의 배수를 n까지 모두 제외한 후에 소수를 판별하는 것이 에라토스테네스의 체 알고리즘이다.
         */
        primBool = new boolean[n+1];//boolean 배열을 초기화 하지 않을 경우 모두 false

        //배열은 0부터 시작한다. 하지만 자연수는 1부터 시작함으로 0은 아에 제외시킼고 1은 소수가 아님으로 true로 만든다.
        primBool[0] = primBool[1] = true;

        for(int i=2; i<=Math.sqrt(n); i++){
            //이미 true로 합성수로 판별이 되었다면 넘어간다.
            if(primBool[i] == true){
                continue;
            }

            /*
            해당 소수의 배수를 모두 true로 변경합니다.
            첫 수를 i+i가 아닌 i*i로 하는 이유는 속도 때문인데
            3+3의 경우 3*2로 이미 true이고
            4+4,4+4+4의 경우 4*2,4*3으로 이미 true이고
            5+5,5+5+5,5+5+5+5의 경우 5*2,5*3,5*4로 이미 true입니다.
            합성수의 제곱보다 작은 배우의 경우 이미 그 전에 합성수로 판별된 특징이 있습니다.
             */
            for(int j = i*i; j<primBool.length; j+=i){
                primBool[j] = true;
            }
        }
    }

}

 

최대한 주석에 자세히 설명해 놓으려고 했지만 한번 더 설명을 하겠습니다. 가장 큰 개념은 배열을 입력받은 두 번째 숫자까지 만든 후에 그 0~입력받은 마지막 수만큼 소수인지 아닌지 체크하면서 해당 index번호가 소수이면 false 아니면 true로 입력하는 방식입니다.

1. 왜 첫수부터 마지막 수까지만 배열을 만들지 않고 0부터 만들어서 자원을 낭비하는가?

더하기 빼기가 귀찮고 더 번거롭습니다.(해봤더니 위 방식이 제일 편합니다.) 어차피 해당 알고리즘을 사용하면 비용은 정말 많이 감소해서 크게 손해보지 않는다고 생각합니다.

2. 왜 헷갈리게 소수면 true, 합성 수면 false로 하지 않고 반대로 했는가?

boolean을 초기화하지 않고 처음에 선언하면 모두 false로 되기 때문입니다.

합성수를 발견하면 true로 변경해주고 아니면 넘어가는 식의 로직이기 때문에 이렇게 표현했습니다. 처음부터 배열을 모두 true로 변경하시거나 로직을 반대로 합성수를 발견하면 내버려 두고 아니면 true로 변경하는 식의 로직을 짜셔도 무방합니다. 하지만 코드의 길이가 늘어날 것입니다.

 

3. 어떻게 합성수를 모두 제외하나요?(에라토스테네스의 체)

모든 합성수를 true로 만들어야만 해당 문제를 해결할 수 있습니다.

합성수를 구하기 위해서는 몇가지 특징을 미리 아셔야 하는데 합성수는 일단 소수의 곱입니다.

예를 들어 4=2*2 입니다. 2라는 소수의 곱이죠 15=3*5입니다. 3과 5라는 소수의 곱이죠 이렇게 합성수는 소수의 곱으로 나타낼 수 있습니다.

근데 여기서 가만히 생각해 보면 15=3*5인데 이게 어떻게 보면 3을 5번 더해라 라는 의미가 됩니다. 3+3+3+3+3인 거죠 

30=2*3*5입니다. 근데 사실 2를 15번 더하는 식으로 표현 할 수 있습니다. 이처럼 합성수는 소수의 배수로 표현할 수 있습니다.

이때 기준이 되는 소수가 √n(제곱근) 보다 작은 수에서 나온다는 특징이 있습니다. 예를 들어 26이면 8보다 작은 수가 기준이 된다는 것입니다. 실제로 2가 기준에 되어 2의 13배로 표현할 수 있습니다. 39에 경우 7보다 작은 3의 13배로 표현할 수 있습니다. 이를 이용해 주어진 수의 제곱근보다 작은 수만큼 반복문을 돌려 배수를 모두 true로 변경해주면 합성수를 모두 제외할 수 있게 됩니다.

 

감사합니다.