[백준] 1929번 : 소수 구하기

---

* "소수로 판별된 수의 배수는 이미 소수가 될 수 없다." 는 것. 

* N이 소수인지를 판단하기 위해서는 2~N의 제곱근 까지의 수 중에서 약수를 가지지 않아야 한다.

즉, N의 제곱근 까지만 판단.

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main{

    public static boolean[] prime;

    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());

        prime = new boolean[N + 1]; // 0 ~ N
        makePrice();

        for(int i=M; i<=N; i++){
            if(!prime[i]){
                bw.write(i+" ");
            }
        }
        bw.flush(); bw.close();

        
    }

    public static void makePrice(){
        prime[0] = prime[1] = true; // 0, 1 : Prime X

        // 2 ~ N 제곱근
        for(int i=2; i<=Math.sqrt(prime.length); i++){
            if(prime[i] == true) {continue;} // 소수 X => pass
            for(int j = i*i; j<prime.length; j+=i){
                prime[j] = true; // 소수의 배수 => 소수 X
            }
        }
    }

} // Main