문제 설명

문제 분석

<aside> 💡 N의 제곱근까지만 탐색하는 이유

N이 ab라고 가정했을 때, a와 b 모두 N의 제곱근보다 클 수 없다. 따라서 N의 제곱근까지만 확인해도 전체 범위의 소수를 판별할 수 있다. 만약 16의 범위까지 소수를 구할 때 16 = 44로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게 된다는 뜻이 된다. 따라서 4까지만 확인하고 소수 판별을 진행하면 된다.

</aside>

슈도코드

구현

public class 소수_구하기 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int M = scan.nextInt(); // 시작 수
        int N = scan.nextInt(); // 종료 수
        int[] primes = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            primes[i] = i;
        }

        for (int i = 2; i <= Math.sqrt(N); i++) {
            // 소수가 아님
            if (primes[i] == 0) continue;

            // 소수가 아니라는 것을 표시
            for (int j = i + i; j <= N; j += i) {
                primes[j] = 0;
            }
        }

        for (int i = M; i <= N; i++) {
            if (primes[i] != 0) {
                System.out.println(primes[i]);
            }
        }
    }
}