[백준 | Java] 1929 소수 구하기

내 풀이

이 문제는 M부터 N까지의 숫자 사이의 소수들을 모두 출력해야하기 때문에
에라토스테네스의 체를 사용해 N보다 작은 소수들을 구한 다음, M보다 큰 소수들만 출력하는 방법으로 풀었다.

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(), " ");
        StringBuilder sb = new StringBuilder();

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

        boolean[] isPrime = new boolean[N+1];

        //0과 1은 소수가 아니므로 2부터 default값을 true로 바꿔줌
        for (int i = 2; i < isPrime.length; i++) {
            isPrime[i] = true;
        }

        //2부터 N의 제곱근까지의 모든 수 확인
        for (int i = 2; i <= Math.sqrt(N); i++) {
            //해당 수가 소수라면, 해당 수를 제외한 배수들을 모두 false 처리
            for (int j = i*i; j <= N; j += i) {
                isPrime[j] = false;
            }
        }

        for (int i = 0; i < isPrime.length; i++) {
            if (i >= M && isPrime[i] == true) {
                sb.append(i).append('\n');
            }
        }
        System.out.println(sb);
    }
}