Java 1929 소수 구하기

 

풀이 :

입력 값이 1,000,000 까지기 때문에 범위를 1,000,000까지 잡고 소수를 구하게 되면 시간내에 수행할 수 없는 문제이다.

범위를 n의 제곱근 값까지만 설정한 뒤 계산하였다.

 

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        for(int i = n; i <= m; i++){
            if(getPrime(i)){
                System.out.println(i);
            }
        }

    }
    public static boolean getPrime(int n){
        if(n < 2){
            return false;
        } else if(n == 2){
            return true;
        }
        for(int i = 2; i <= Math.sqrt(n); i++){
             if(n%i == 0){
                return false;
            }
        }
        return true;
    }
}