[문제 풀이] 백준 1929번 소수 구하기 JAVA

백준 1929번 소수 구하기 문제는 자연수 M과 N을 입력 받고 M~N에 존재하는 소수를 모두 출력하는

코드를 작성하는 문제이다.

 

처음 접근은 기본 소수 판별법으로 3~16이 주어졌다면 각각 1~3, 1~16까지 나누어서 소수인지 아닌지 판별하는 방법으로 접근하였다. 하지만 시간초과가 나와서 확인해보니  M,N이 최대 1,000,000 까지 가능해서 반복문을 이중으로 사용할 수 가 없었다.

 

< 초기 코드 >

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int m=s.nextInt();
        int n=s.nextInt();
        decimal(m,n);
        
    }
    public static void decimal(int m,int n){
        for(int i=m;i<=n;i++){
            int cnt=0;
            for(int j=1;j<=i;j++){
                if(i%j==0)cnt++;
            }
            if(cnt==2)System.out.println(i);
        }
    }
}

 해당 코드가 시간초과가 나와서 찾아보니 소수를 판별하는 방식에는 여러 방식이 존재하였고

그중에는 에라토스테네스의 체라는 알고리즘이 있다는 것을 확인하였다.

그래서 검색해서 개념을 확인후 이해한대로 코드를 작성해보았다.

 

< 에라토스테네스의 체 ver.생각한데로 구현 >

import java.util.*;
import java.util.stream.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int m=s.nextInt();
        int n=s.nextInt();
        decimal(m,n);
        
    }
    public static void decimal(int m,int n){
        // int num[]=new int[n];
        // Arrays.setAll(num,index->index+1);
        List<Integer> list=IntStream.rangeClosed(1,n).boxed().collect(Collectors.toList());
        
         for(int i=1;i<list.size();i++){
             int k=list.get(i);
             for(int j=i;j<list.size();j++){
                 if(list.get(j)%k==0&&list.get(j)!=k){list.remove(list.get(j));}
             }
         }
        for(int i=0;i<list.size();i++){
            System.out.println(list.get(i));
        }
    }
}

에라토스테네스의 체라는 알고리즘은 소수를 제외한 소수의 배수를 차례로 제거하는 방식을 사용하는 것을 확인하였다.

그래서 List를 이용해서 입력받은 범위의 수를 넣어준 후 List에서 소수의 배수를 차례로 제거했다.

먼저 1을 제외시킨 후 2를 제외한 2의 배수를 제거하였다. 순서대로 3을 제외한 3의 배수, 4는 이미 제거 되었기 때문에

5를 제외한 5의 배수 이런식으로 접근해 코드를 작성한 결과 시간초과가 발생하였다.

 

그 이유를 확인해보니 시간 복잡도를 줄이기 위해서 사용했던 list.remove(list.get(j));가 연산할 때마다 O(N)만큼 발생하여

for문과 합치면 O(N³)이라는 결과를 초래하고 말았다.

본인이 작성한 코드는 에라토스테네스의 체 개념을 일부 반영하고 있지만 정확한 것은 아니었고 코드 구성 중

비효율적인 부분들로 시간복잡도를 증가 시키고 있었다.

 

이러한 문제를 해결하고자 에라토스테네스의 체 알고리즘을 다시 공부하고 코드를 작성하였다.

 

< 에라토스테네스의 체 ver.구현 성공 >

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        int m = s.nextInt();
        int n = s.nextInt();
        sieveOfEratosthenes(m, n);
    }

    public static void sieveOfEratosthenes(int m, int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true); 

        isPrime[0] = isPrime[1] = false; 

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) { 
                for (int j = i * i; j <= n; j += i) { 
                    isPrime[j] = false;
                }
            }
        }

        
        for (int i = m; i <= n; i++) {
            if (isPrime[i]) {
                System.out.println(i);
            }
        }
    }
}

이처럼 에라토스테네스의 체 알고리즘을 적용하여 코드를 작성할 경우 시간복잡도는 O(n log log n)으로 

처음에 작성한 코드보다 약 166,667배 정도 속도가 빠르다는 것을 확인할 수 있었다.

위의 코드를 잠깐 설명하자면 boolean형의 isPrime 배열을 입력받은 수 n+1만큼의 길이로 선언한다.

이 배열에 처음은 true(소수)로 설정 후 순서대로 소수를 제외한 소수의 배수를 제거하는 흐름이다.

i=2라면 j=4부터 시작해 소수를 제외한 배수를 false로 바꾸는 것을 확인할 수 있으며

if (isPrime[i])은 조건을 통해서 이미 false 즉, 소수에서 제외된 수들을 중복해서 연산하는 것을 최소화 시켜주는 

조건문이다.

여기서 핵심은 for (int j = i * i; j <= n; j += i) 문 그리고 for (int i = 2; i * i <= n; i++) 에서 i * i <= n 제곱근 만큼만 

반복해서 연산을 최소화 시켜주는 것이 핵심이라 생각한다.

 

해당 문제의 여러 풀이들을 찾아보았지만 대부분이 에라토스테네스의 체 알고리즘을 사용하는 방식이었다.

에라토스테네스의 체를 사용하지 않고 푸는 방법도 존재하긴 하지만 시간복잡도에 있어서 비효율적이다.

 

 

이후 다시 해당 문제를 풀어보았는데 

위와 같이 에러가 굉장히 많이 났다. 하지만 코드를 다시쳐보니 통과했고 이전 에러가 났던 코드와 비교해보았지만

별다른 차이가 없는 것을 확인한 이상한 문제라고 생각할뻔 했다.

 

< 초기 코드 > 

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int n = s.nextInt();
        int m = s.nextInt();

        boolean prime[] = new boolean[m + 1];

        primeTool(prime);

        for (int i = n; i <= m; i++) {
            if (prime[i]) sb.append(i+"\n");
        }

        System.out.print(sb);
    }

    public static void primeTool(boolean prime[]) {
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;

        for (int i = 2; i < prime.length; i++) {// 문제의 부분
            if (prime[i]) {
                for (int j = i * i; j < prime.length; j += i) {
                    prime[j] = false;
                }
            }
        }
    }
}

 

본 코드는 에라토스테네스의 체를 통해서 소수를 미리 범위만큼 구한 후 n~m사이의 소수만을 출력하는 방식이다.

위에서는 별다른 문제를 찾지 못했다고 했지만 생각지도 못한곳이 틀린것을 확인했다. 앞서 여러 에라토스테네스의 체관련 문제를 풀이했고 별다른 문제가 없서 위와 같이 계속 구현하고 있었는데 문제의 부분이라고 주석처리 된 곳에서 문제가 발생하는 것이다.  for (int i = 2; i < prime.length; i++)는 int 오버플로우 가능한 부분이었다. 이전에는 조건이나 입력의 차이 때문에 에러가 발생하지 않았지만 이번 문제에서는 발생한 것으로 보인다.

문제있는 부분을  for (int i = 2; i *i < prime.length; i++)로 바꾸고 코드를 제출해본 결과 맞았다는 결과를 받을 수 있었다.

수정한 코드는 다음과 같다.

 

< 최종 코드 > 

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int n = s.nextInt();
        int m = s.nextInt();

        boolean prime[] = new boolean[m + 1];

        primeTool(prime);

        for (int i = n; i <= m; i++) {
            if (prime[i]) sb.append(i+"\n");
        }

        System.out.print(sb);
    }

    public static void primeTool(boolean prime[]) {
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;

        for (int i = 2; i *i < prime.length; i++) {
            if (prime[i]) {
                for (int j = i * i; j < prime.length; j += i) {
                    prime[j] = false;
                }
            }
        }
    }
}

문제를 해결하고보니 예전 코드에서도 i*i로 접근했던 것을 확인할 수 있었다.

 

마무리

해당 문제는 에러를 해결하려고 시간을 굉장히 많이 투자한 문제이다. 하지만 틀린 코드와 맞은 코드를 비교했을때 틀린점이 없다고 생각했다. 하지만 에러가 발생할 수도 있는 위험 코드가 존재했고 이부분을 해결해 문제를 잘 마무리 할 수 있었다.