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

문제

1929번: 소수 구하기

---

 

접근 방법

1. 소수를 미리 구해두기 위해서 에라토스테네스의 체를 이용하여 미리 소수를 찾아놓습니다.

2. 범위를 탐색하며 소수가 있으면 해당하는 인덱스를 출력해줍니다.

 

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

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int M,N;
    private static boolean[] isPrime = new boolean[1000010];

    //에라토스테네스의체
    public static void eratosthenes(){
        isPrime[0] = isPrime[1] = false;

        for(long i = 2 ; i <= 1000000 ; i++){
            if(!isPrime[(int)i]) continue;

            for(long j = i*i ; j <= 1000000 && j >0 ; j+=i){
                isPrime[(int)j] = false;
            }
        }
    }

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        Arrays.fill(isPrime, true);
        eratosthenes();
    }

    //실행
    public static void process() {
        for(int i = M ; i <=N ; i++){
            if(isPrime[i]){
                sb.append(i).append("\n");
            }
        }
        System.out.println(sb);
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}