[Java] 백준(실버-3) 1929번 - 소수 구하기

입출력 예시

Input
3 16

Output
3
5
7
11
13

문제 풀이

---

이 문제에서는 M과 N의 범위(최대 1,000,000) 및 제한 시간(2초)을 생각했을 때 완전탐색을 활용해 2부터 하나하나 나눠보는 것은 O(N^2)의 시간복잡도를 기지므로 시간초과가 발생하게 된다. 완전탐색 보다는 소수를 구할 때 효울적인 ‘에라토스테네스의 체’ 알고리즘을 활용해야 한다.

에라토스테네스의 체를 활용해 도출한 아이디어는 다음과 같다.

• 실행 시간을 줄이기 위해 불필요한 반복을 줄여야한다.
• M부터 N까지 모든 수를 반복하며 마킹할 필요없이 마킹할 수의 제곱근 만큼만 반복한다.
• 마킹된 수의 배수는 소수가 아니기에 검증하지 않는다.
• 마킹이 안된 수(소수)만 출력한다.

아이디어를 통해 코드를 작성해보자.

boolean[] prime_arr = new boolean[N+1];
prime_arr[0] = prime_arr[1] = true;

먼저 2부터 N까지 반복하며 마킹을 기록할 배열을 선언하고, 0과 1은 소수가 아니기에 true로 마킹한다.

for(int i=2; i<=Math.sqrt(N); i++) {
    for(int j=i+i; j<prime_arr.length; j+=i) {
        prime_arr[j] = true;
    }
}

그리고 2부터 N의 제곰근까지 반복하면서 소수가 아닌 수의 위치에 true로 마킹한다.

for(int i=M; i<prime_arr.length; i++) {
    if(prime_arr[i] == false) bw.write(i+"\n");
}

그렇게 2부터 N까지 마킹된 배열에서 M번째 인덱스부터 마킹이 안된 수인 소수를 출력하면 된다.

작성코드

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        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());

        boolean[] prime_arr = new boolean[N+1];
        prime_arr[0] = prime_arr[1] = true;

        for(int i=2; i<=Math.sqrt(N); i++) {
            for(int j=i+i; j<prime_arr.length; j+=i) {
                prime_arr[j] = true;
            }
        }

        for(int i=M; i<prime_arr.length; i++) {
            if(prime_arr[i] == false) bw.write(i+"\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• O(NloglogN)의 시간복잡도를 가진 에라토스테네스의 체를 활용해 제한시간 2초에 맞춰 문제를 풀 수 있었다.