[BaekJoon-1929] 소수구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

3 16

예제 출력 1

풀이

구간의 모든 수를 따로 나누어 소수인지 검사하면 같은 약수를 반복 확인한다. N이 최대 1,000,000이므로 합성수를 한꺼번에 표시하는 체가 적합하다.

그래서 에라토스테네스의 체를 이용하여 문제를 해결할 수 있다.

에라토스테네스의 체는 2부터 시작해 각 소수의 배수를 합성수로 표시한다. 표시되지 않은 2 이상의 수만 출력하면 된다.

왜 제곱부터 배수를 지우나

N 이하의 모든 수를 각각 나눠 보는 대신 2부터 소수의 배수를 한 번에 합성수로 표시한다. 2에서 4,6,8,…을 지우고, 다음 소수 3에서 9,12,15,…을 지운다. 3의 배수 6은 이미 2에서 지웠으므로 3²부터 시작해도 빠진 수가 없다. 일반적으로 p보다 작은 소인수가 있는 p의 배수는 앞선 단계에서 표시된다.

N=16이면 2의 제곱 4부터 짝수를 표시하고, 3의 제곱 9부터 3의 배수를 표시한다. 4²은 16을 넘으므로 더 볼 필요가 없다. 남은 2,3,5,7,11,13이 소수이고, 입력 M=3이면 3부터 출력한다. 1은 소수가 아니므로 코드의 출력 시작값을 max(2,M)로 잡았다.

안쪽 반복이 prime * prime부터 시작하고 바깥 반복도 제곱이 N 이하일 때만 돌아간다. 체의 시간 복잡도는 O(N log log N), 합성수 표시 배열은 O(N) 공간이다. N이 1이면 반복 없이 아무 줄도 출력하지 않는다. 한 줄씩 즉시 쓰지 않고 출력 버퍼에 모아 표준 출력 호출도 줄였다.

N=16을 손으로 따라가면 2에서 4,6,8,10,12,14,16을 표시한다. 다음 3에서는 9와 12,15를 검사하지만 12는 이미 표시돼 있어도 다시 표시해도 된다. 4는 이미 합성수이므로 건너뛰고, 5²=25가 16보다 커진 시점에 배수 표시를 끝낸다.

왜 √N에서 멈춰도 될까? 합성수 x=pq에서 두 인수 p와 q가 모두 √x보다 클 수는 없다. 적어도 하나는 √x 이하다. 따라서 N 이하의 합성수라면 √N 이하인 소수의 배수 표시 과정에서 이미 지워진다. 코드는 이 수학적 경계를 prime * prime <= n으로 표현한다.

소스코드

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

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

        boolean[] composite = new boolean[n + 1];
        for (int prime = 2; prime * prime <= n; prime++) {
            if (composite[prime]) continue;
            for (int multiple = prime * prime; multiple <= n; multiple += prime) {
                composite[multiple] = true;
            }
        }

        StringBuilder out = new StringBuilder();
        for (int value = Math.max(2, m); value <= n; value++) {
            if (!composite[value]) out.append(value).append('\n');
        }
        System.out.print(out);
    }
}