백준 1929 - 소수 구하기 - 에라토스테네스의 체 ( Java )

 

besforyou

 

---

문제 풀이

 

M, N을 입력받고 M과 N 사이 소수를 모두 출력하는 문제입니다.

 

이 문제는 에라토스테너스의 체를 적용하면 매우 빠르게 풀어낼 수 있습니다.

 

 

에라토스테네스의 체

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 
2. 2를 제외한 모든 2의 배수를 지운다.
3. 남아있는 수 가운데 3을 제외한 모든 3의 배수를 지운다.
4. 위 과정을 반복한다.

N까지의 소수를 구한다고 치면 M * M > N 을 만족하는 M의 배수들 까지만 지워도 정답을 구할 수 있다.

 

예로, 120까지의 소수를 구한다고 치면, 11 * 11 > 120 이므로 11의 배수들 까지만 지워도 소수들만 구할 수 있다.

 

 

코드

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int N, M;
    static boolean notPrimeNum[];
 
    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());
 
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
 
        notPrimeNum = new boolean[N+1];
        notPrimeNum[0] = notPrimeNum[1] = true; // 0, 1은 소수가 아니므로 true
 
        for (int i = 2 ; i * i <= N ; i++) {
            if (notPrimeNum[i] == false)    // i 가 소수라면
                for (int j = i * i ; j <= N ; j += i ) // i * 2는 2의 배수를 제외할때 이미 제외됬으므로 i * i부터 시작
                    notPrimeNum[j] = true;    // i를 제외한 i의 모든 배수를 소수에서 제외
        }
 
        for (int i = M ; i <= N ; i++) {    
            if (notPrimeNum[i] == false) bw.write(i + "\n");    // 소수 모두 출력
        }
 
        bw.flush();
        bw.close();
    }
}