BOJ/1929) 소수 구하기

소수 구하기(1929), Silver2

https://www.acmicpc.net/problem/1929

문제풀이

소수를 구하는 방법은 여러가지가 있지만, 에라토스테네스의 체를 활용하여 소수를 구하였다.
소수는 1과 자기 자신만을 약수로 갖는 수를 뜻한다. 따라서 소수가 아닌지(합성수인지)를 확인하려면 1과 자기자신 외 다른 수의 배수인지를 확인하면 된다.
결론은 에라토스테네스의 체는 소수를 찾고, 그 소수의 배수를 모두 지워나가는 방식으로 진행하면 된다.

소스코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int M = Integer.parseInt(input[0]);
        int N = Integer.parseInt(input[1]);
        br.close();
        
        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        // 에라토스테네스의 체
        for(int i = 2; i < N; i++) {
            if (!isPrime[i]) continue;
            for(int j = i + i; j <= N; j += i) {
                isPrime[j] = false;
            }
        }
        // 답 출력
        for(int i = M; i <= N; i++) {
            if (isPrime[i]) System.out.println(i);
        }
    }
}