[JAVA] 백준 1929. 소수 구하기

이 글은 읽는데 약 5분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

풀이

문제 자체는 간단하다. 관건은 아마도 빠르게 찾는 것이 아닐까.
간단한 문제임에도 정답률이 20%대로 낮으며

시간 초과가 상당히 많다.

나는 두 가지 방법으로 풀어봤다. 사실 인터넷 찾아보니 에라토스테네스의 체로 풀어야 시간 초과가 안난다는 글들이 있는데 나는 그냥 반복문 돌려서 O(sqrt(n))의 시간복잡도로 풀었는데도 넉넉하게 통과됐다(아래 참고). 뭔가 바꼈나?

하여튼 두 방법 모두 설명 해보겠다.

반복문으로 소수 판별

[JAVA] 백준 4134. 다음 소수
※개인 공부 목적의 정리글입니다.이 글의 내용이 최선의 해답은 아닐 수 있습니다. 문제 정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오. 입
yuria.dev

사실 이 방법은 이전에 풀었던 문제에서 소수인지 확인하는 부분 그대로 들고와서 풀었다.
위 글에서 만들었던 isPrime 함수를 그냥 범위내의 수에대해 모두 실행해서 출력했는데

뭐… 시간이 너무 넉넉하다. 핵심 코드는 위 글과 똑같으니 입력 부분이랑 범위 반복 돌리는 부분만 바꿔주면 되므로 따로 안올린다.

에라토스테네스의 체 이용

에라토스테네스의 체라는 것이 있다. 어떤 방법으로 소수가 아닌 수들을 제외 시키는 것인데, 이것은 범위내의 대량의 수가 소수인지 판단할 때 사용하기 매우 좋다.

범위가 있으므로 그 범위의 수를 모두 나열한 다음 소수가 아닌 수들을 지우면 소수만 남은 배열이 되고, 이후 주어진 숫자를 단지 이 배열에 소수로 나타나는지만을 검사하면 되므로 매우 빠를 것이다.

그렇다면 에라토스테네스의 체를 만드는 과정은 무엇일까?

  1. 범위내의 수를 모두 나열한다.
  2. 1은 소수가 아니므로 제외한다.
  3. 2이상 \(\sqrt {N}\)이하 각 수의 배수를 지우되, 자기 자신은 지우지 않는다.
    또한 이미 수가 지워져있으면 건너뛴다.
  4. 이를 끝까지 반복하면 소수만 남게된다.

방법은 매우 간단하며, 이것을 코드로 구현해야한다. 나는 이렇게 구현했다.

1. N+1 크기의 빈 int 배열을 선언(기본적으로 0으로 초기화됨)
2. 2부터 배열 끝까지 돌면서 배열의 값을 현재 인덱스와 같게 지정
3. 반복문으로 2이상 sqrt(N)이하 순회
4. 만약 현재 수가 지워져있으면 continue
5. 아니면 현재 수의 다음 배수부터 범위 끝 내에있는 모든 배수를 지움

처음 배열 선언시 크기를 N+1로 잡는 이유는 나중에 소수 판별시 원하는 숫자를 바로 인덱스로 쓰기 위함이다. 배열은 0부터 시작하므로 크기를 N만큼 하면 마지막 인덱스가 N-1이 되어서 N이 소수인지 확인하기 위해서 arr[N]으로 접근하면 범위를 벗어나 에러가 나기 때문이다.
인덱스 0번 자리를 안쓰는 대신 마지막에 자리를 하나 늘린 것이다.

배열의 값을 현재 인덱스와 같게 지정하는 것도 검사하고자 하는 숫자를 바로 인덱스에 넣었을 때 그 숫자가 해당해야하기 때문이다.
만약 3을 검사한다면 arr[3]으로 접근하기 위함. 이렇게 하면 배열상으로는 네번째 칸이지만 실제로 들어있는 숫자는 3이다.

또한 2부터 시작하는 이유는 1은 소수가 아니므로 이미 0으로 초기화 된 값을 건들 필요가 없기 때문이다.

2부터 \(\sqrt {N}\)이하를 순회한다. 현재 숫자를 i로 하겠다.

만약 i가 이미 지워졌으면(값이 0이면) 그냥 건너뛴다.

아니면 i의 다음 배수인 i*2부터 배열의 끝 값 까지 돌되, 배수만 지워야 하므로 j의 증감을 i만큼 커지도록 하며 지운다.

public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    
    int[] primes = new int[1_000_000];
    for(int i=2; i<primes.length; i++){
        primes[i] = i;
    }
    
    for(int i=2; i<=1000; i++){  // sqrt(1_000_000) = 1_000
        if(primes[i] == 0) continue;
        
        for(int j=i*2; j<=1_000_000; j+=i){
            primes[j] = 0;
        }
    }
    
    String[] input = br.readLine().split(" ");
    int N = Integer.parseInt(input[0]);
    int M = Integer.parseInt(input[1]);
    
    for(int i=N; i<=M; i++){
        if(primes[i] != 0){
            sb.append(i);
            sb.append("\n");
        }
    }
    
    System.out.println(sb.toString());
    br.close();
}

위 과정을 문제에 맞게 코드로 변환했다.

처음 한 번만 에라토스테네스의 체를 만든 후, 이후에는 범위 내의 숫자 각각이 체에서 0인지 아닌지만 확인하면 소수 여부가 판별된다.

시간 또한 위의 방법보다 훨씬 짧은 것을 볼 수 있다.

댓글