백준 1929번: 소수 구하기

문제 출처: https://www.acmicpc.net/problem/1929

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = reader.readLine().split(" ");
        int M = Integer.parseInt(arr[0]);
        int N = Integer.parseInt(arr[1]);
        StringBuilder builder = new StringBuilder();
 
        // 모든 자연수는 소수들의 곱으로 표현이 되기 때문에, 
        // 2부터 N-1까지의 수 중에서 2의 배수를 모두 체로 거르고 남은 숫자들 중에서 3의 배수로 거르고를 반복해 
        // sqrt(N)까지 나눠서 남은 걸러지지 않고 남은 수들이 모두 소수가 된다. 
        // 출처: http://ledgku.tistory.com/61 [견우와 직녀]
        boolean[] isPrimeArr = new boolean[N+1];
        Arrays.fill(isPrimeArr, true);
        isPrimeArr[0] = false;
        isPrimeArr[1] = false;
        
        for(int i=2 ; i<=(int)Math.sqrt(N) ; ++i) {
            if (isPrimeArr[i]){
                for (int j=i+i; j<=N; j+=i)
                    isPrimeArr[j] = false;
            }
        }
        
        for(int i=M ; i<=N ; i++){
            if(isPrimeArr[i])
                builder.append(i).append("\n");
        }
        
        System.out.println(builder);
    }
}