백준 1929 소수 구하기

시간초과가 뜨지 않게 소수를 구하려면 에라토스테네스의 체 방법이 필요하다.
소수는 1과 자기자신만을 약수로 가지는 수이다.
for문을 돌리면서, 2부터 해당값까지 배수인 숫자들을 모두 true로 반환한다.
여기서 해당값이 𝑝 곱하기  𝑞라면 결과적으로 𝑝 와 𝑞 중 하나는 반드시 √N 보다 작거나 같다.
즉, √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면 이는 1 과 N 을 제외한 다른 자연수가 N 의 약수라는 의미이므로 소수가 아니게 되는 것이다.

import java.util.Scanner;

public class Main {
    public static boolean[] prime;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input= new Scanner(System.in);
        int m = input.nextInt();
        int n = input.nextInt();
        prime = new boolean[n+1];
        get_prime();
        for(int i = m; i <= n; i++) {
            // false = 소수 
            if(!prime[i]) System.out.println(i);
        }
    }

    static void get_prime() {
        prime[0] = prime[1] = true;
        for(int j=2; j<Math.sqrt(prime.length)+1; j++) {
            if(prime[j])continue;
            for(int i = j+j; i<prime.length; i+=j) {
                prime[i]=true;
            }
        }


    }

}