1929번: 소수 구하기

문제

M 이상 N 이하의 소수를 모두 출력하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어집니다. (1 ≤ M ≤ N ≤ 1,000,000)
• 출력: 한 줄에 하나씩, 증가하는 순서대로 소수를 출력합니다.

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

풀이: 에라토스테네스의 체를 활용한 빠른 소수 판별

탐색해야 하는 수의 최댓값이 1,000,000으로 매우 크고, 구간 내의 '모든' 소수를 구해야 하므로 각각의 수를 개별적으로 판별하는 대신 '에라토스테네스의 체' 알고리즘을 사용하는 것이 가장 효율적입니다.

• 배열 초기화: 1,000,000까지의 수를 판별하기 위해 크기가 1,000,001인 boolean 배열 p를 선언합니다. 자바에서 boolean 배열의 기본값은 false이므로, false를 소수로, true를 합성수(소수가 아닌 수)로 취급하여 진행합니다.
• 예외 처리: 숫자 1은 소수가 아니므로 p[1] = true로 명시적 처리를 해줍니다.
• 에라토스테네스의 체 최적화 로직:
  • 2부터 최대 탐색 범위의 제곱근인 1,000까지만 순회합니다. (어떤 수의 약수는 항상 짝을 이루므로, 1,000까지만 검사해도 1,000,000 이하의 모든 합성수를 걸러낼 수 있습니다.)
  • 현재 수 i가 이미 합성수로 판별되었다면(p[i] == true) 건너뜁니다.
  • 현재 수 i가 소수라면, 자기 자신을 제외한 i의 배수들(2 * i부터 시작)을 모두 합성수(true)로 마킹하여 체로 거르듯 지워나갑니다.
• 결과 출력: 모든 체의 마킹이 끝난 후, 입력받은 n부터 m까지 순회하며 값이 false(소수)인 인덱스만 BufferedWriter를 통해 출력합니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       // false: 소수, true: 합성수로 사용
       boolean[] p = new boolean[1000001];
       p[1] = true; // 1은 소수가 아님
       
       // 에라토스테네스의 체 알고리즘 적용 (제곱근까지만 탐색하여 최적화)
       for (int i = 2; i <= 1000; i++) {
          if (p[i])
             continue;
             
          // i가 소수라면, i의 배수들을 모두 합성수로 마킹
          for (int j = 2 * i; j <= 1000000; j += i) {
             p[j] = true;
          }
       }

       StringTokenizer st = new StringTokenizer(br.readLine());
       int n = Integer.parseInt(st.nextToken());
       int m = Integer.parseInt(st.nextToken());

       // n부터 m까지 소수인 숫자만 찾아 출력
       for (int i = n; i <= m; i++) {
          if (!p[i]) {
             bw.write(i + "\n");
          }
       }

       bw.flush();
    }
}

알고리즘 분류

수학 (Mathematics), 정수론 (Number Theory), 에라토스테네스의 체 (Sieve of Eratosthenes)