[BOJ] 백준 1929번 : 소수 구하기 (JAVA)

문제

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

입력

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

출력

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

 

풀이

일반적인 소수 알고리즘이 아닌 최적화된 알고리즘을 사용해야 했습니다. 우리가 흔히 소수를 구할 때는 2 이상 (N - 1)이하의 자연수를 모두 나누어 떨어지는지 확인하는 경우가 많습니다.

하지만, 위에서 N은 최대 10^6 이었고, 이것은 O(10^12)이므로 주어진 제한 시간인 2초 안에 통과할 수가 없습니다.

따라서 일반적인 소수 알고리즘이 아닌, 에라토스테네스의 체를 이용한 최적화된 알고리즘을 사용해야 합니다.

에라토스네테스의 체에 관한 상세한 설명은 여기서 확인하실 수 있습니다.

간단히 말하면, 소수에 해당하는 수의 배수를 모두 합성수로 처리하여 고려를 하지 않는 것입니다. 예를 들어, 가장 처음 소수는 2이므로 4, 6, 8, ... 과 같은 2의 배수를 모두 합성수로 처리합니다. 그 다음 소수는 3이므로 6, 9, 12, ... 와 같은 3의 배수를 모두 합성수로 처리하는 것입니다. 소수일 경우 true, 합성수일 경우 false로 초기화하여 배열을 true와 false로 분류를 하면 됩니다.

에라토스테네스의 체의 시간복잡도는 얼마일까요? 바로, O(NloglogN)으로, O(N^2)보다 많이 줄일 수 있습니다. 그래서 N이 10^6일지라도 문제 없이 통과할 수 있는 것입니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        ArrayList<Boolean> primeList;
 
        primeList = new ArrayList<Boolean>(N + 1);
 
        // 0과 1은 소수도, 합성수도 아님.
        primeList.add(false);
        primeList.add(false);
 
        // 2이상의 수는 전부 소수라고 가정.
        for (int i = 2; i <= N; i++) {
            primeList.add(i, true);
        }
 
        for (int i = 2; (i * i) <= N; i++) {
            if (primeList.get(i)) { // i가 소수일 경우, i를 제외한 i의 배수를 모두 합성수로 초기화.
                for (int j = i * i; j <= N; j += i)
                    primeList.set(j, false);
            }
        }
 
        // 소수인 것만 출력.
        for (int i = M; i <= N; i++) {
            if (primeList.get(i)) {
                bw.write(i + "\n");
            }
        }
 
        bw.flush();
        br.close();
        bw.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.