[백준] 1929 : 소수 구하기 - Java

• 백준 문제 URL

m 이상 n 이하의 모든 소수를 출력하는 문제
주어진 범위에서 에라토스테네스의 체를 이용해 효율적으로 소수를 구함.

---

문제 접근

• 입력
  첫 줄에 m n (1 ≤ m ≤ n ≤ 1,000,000)
  m 이상 n 이하의 모든 소수를 출력해야 함.

  예를 들어,

  3 10

  입력 시, 출력은 3 5 7이 됨.

• 출력
  m 이상 n 이하 소수를 한 줄에 하나씩 출력함.

---

제출

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        
        // 에라토스테네스의 체 초기화
        boolean[] isPrime = new boolean[n+1];
        for(int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }
        isPrime[0] = isPrime[1] = false;
        
        // 배수 제거 
        for(int i = 2; i * i <= n; i++) {
            if(isPrime[i]) {
                for(int j = i * i; j <= n; j += i) {  // j += i가 핵심!
                    isPrime[j] = false;
                }
            }
        }
        
        // m 이상 n 이하 소수 출력
        for(int i = m; i <= n; i++) {
            if(isPrime[i]) {
                System.out.println(i);
            }
        }
    }
}

---

핵심 개념

1. 에라토스테네스의 체(Sieve of Eratosthenes)
   2부터 n까지 배열을 만들고 합성수를 제거해 소수를 찾음.
   시간복잡도 O(n log log n) — n=10^6에서도 빠름.

2. 배수 제거 핵심 로직

   for(i=2; i*i<=n; i++) {
       if(isPrime[i]) {  // i가 소수일 때만
           for(j=i*i; j<=n; j+=i) {  // i의 배수만 제거
               isPrime[j] = false;
           }
       }
   }

3. 3가지 최적화 포인트

   • i*i <= n: √n까지만 검사
   • j = i*i: 이미 제거된 배수 건너뛰기
   • j += i: i의 배수만 정확히 제거 (가장 중요!)

4. 시간복잡도

   • 체 생성: O(n log log n)
   • 출력: O(n)
   • 총 O(n log log n) — n=10^6 통과 보장.

---

출력 예시

입력

3 10

출력

3
5
7

계산 과정:

초기: [F,F,T,T,T,T,T,T,T,T,T]
i=2: 4,6,8,10 제거 → [F,F,T,F,T,F,T,F,F,T,F]
i=3: 9 제거 → [F,F,T,F,T,F,T,F,F,F,F]
m=3~10 중 true: 3,5,7 ✓

---

흔한 실수와 해결

❌ 실수	✅ 해결
j++ 사용	j += i로 i의 배수만 제거
i <= n	i*i <= n으로 √n까지만
j = i*2	j = i*i로 이미 제거된 배수 건너뛰기
int 배열 오버플로우	boolean[] 사용 (메모리 효율적)

---

정리

• 에라토스테네스의 체 패턴의 전형적인 문제임
• j += i가 핵심! 없으면 소수도 제거됨
• √n까지만, i*i부터, i간격으로 3가지 최적화 필수