백준 1929 소수 구하기 Java

이 문제는 정답률 28퍼센트의 소수 구하기 문제이다.

정답률이 28퍼센트인 이유는 아마 에라토스테네스의 체를 쓰지 않고 제출한 분들 때문일 것이다.

이 문제는 에라토스테네스의 체를 쓰지 않고는 시간초과가 나는 문제이다.

 

이 글에선 에라토스테네스의 체를 정리하려고 한다.

소수를 구하는 방법 중 O(루트n)인 방법도 있지만 이 방법도 정수 n 한개가 소수인지 아닌지

구하는데 O(루트n)의 시간이 소요되는 것이다.

따라서 정수 n의 개수가 1000000000 처럼 큰 수 이면 그 수는 실행 횟수는 한 없이 늘어나게 된다.

그래서 여러 수의 소수를 구하는 가장 빠른 방법인 에라토스테네의 체를 사용해야 한다.

 

에라토스테네스의 체에 대해 자세히 설명해주는 다른 블로그나 티스토리가 많다.

간단하게 설명하자면 O(루트n)의 소수를 구하는 방법 처럼

for(int i=2; i*i<=n i++) 의 범위에서 i의 배수를 2~n까지의 배열에서 하나씩 지우는 것이다.

지워지는 수는 소수가 아닌 것이 되는 것이다. 당연히 남아있는 수는 모두 소수이다.

이렇게 한번만 구하면 소수의 개수이든 소수인지 아닌지 구하든 빠른속도로 문제를 해결할 수 있는 것이다.

 

에라토스테네스의 체 코드를 보면

List<Boolean> list = new ArrayList<>();
        list.add(false);
        list.add(false); //0과 1은 소수가 아니다.
        
        //2~n까지 소수로 설정
        for(int i=2; i<=n; i++) 
            list.add(i, true);
        
        //2부터 ~ i*i <= n 각각의 배수들을 지워간다.
        for(int i=2; (i*i)<=n; i++)
            if(list.get(i))
                for(int j=i*i; j<=n; j+=i) //j는 i만큼 증가한다.
                    list.set(j, false);

 이 때 9번 줄에서 for(int i=2; i<=n; i++)로 구할 수 도 있지만 i*i<=n과 속도차이가 많이 나는 것을 볼 수 있다.

게다가 i<=n을 한다면 12번줄인 두 번째 for문에서 j가 int형 범위를 벗어날 수 도 있다.

그렇기 때문에 int j = i*2 등의 조치를 취할 순 있지만

애초에 첫 번째 for문에서 범위를 i*i <= n 으로 설정해주는 것이 간편한 것 같다.

여기선 List<Boolean>을 사용했지만 구현하는 방법은 가지각색이다.

중요한 것은 int i = 2; i*i <= n 의 범위에서 i의 배수들을 모두 지워 준다는 점이다.

 

에라토스테네스의 체의 시간 복잡도는 O(NloglogN)이라고 한다.

loglogN은 수학적 지식이 필요한 문제라고 하니 넘어가도록 하겠다..

에라토스테네스의 체를 사용해서 해결한 소수 구하기 문제의 코드는 아래에 있다.

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m =scan.nextInt();
        int n =scan.nextInt();
        
        List<Boolean> list = new ArrayList<>();
        list.add(false);
        list.add(false); //0과 1은 소수가 아니다.
        
        //2~n까지 소수로 설정
        for(int i=2; i<=n; i++) 
            list.add(i, true);
        
        //2부터 ~ i*i <= n 각각의 배수들을 지워간다.
        for(int i=2; (i*i)<=n; i++)
            if(list.get(i))
                for(int j=i*i; j<=n; j+=i) //j는 i만큼 증가한다.
                    list.set(j, false);
        
        for(int i=m; i<=n; i++){
            if(list.get(i))
                System.out.println(i);
        }
    }