에라토스테네스의 체 [소수 구하기]

📌 백준 1929번: 소수 구하기

오늘은 백준의 1929번 - 소수 구하기 문제를 풀면서
에라토스테네스의 체를 활용하게 되었고, 이에 대해 간단히 정리해보려고 합니다.

---

⏱️ 문제 조건과 제한

• 입력: 자연수 M, N (1 ≤ M ≤ N ≤ 1,000,000)
• 출력: M 이상 N 이하의 소수를 한 줄에 하나씩 출력
• 시간 제한: 2초

---

❌ 일반적인 소수 판별로는 시간 초과

예를 들어, M=3, N=16이라면
단순히 3부터 16까지 모든 수를 순회하며, 매 수마다 소수 판별을 하면

• 각 수 i에 대해 2부터 i-1까지 나눠야 하므로
• 시간 복잡도: O(N^2)

→ 1,000,000 범위에서는 시간 초과 발생합니다.

---

✅ 해결 전략: 에라토스테네스의 체

이 문제는 "소수를 빠르게 구해야 하는 전형적인 문제"입니다.
따라서 에라토스테네스의 체 알고리즘을 적용해야 합니다.

---

🧠 에라토스테네스의 체란?

1부터 √N까지의 수를 기준으로,
그 수의 배수들을 지워가면서 소수만 남기는 방법입니다.

예를 들어, 1 ~ 144까지 소수를 구한다면:

1. 1은 소수도, 합성수도 아니므로 제외
2. 2는 소수이므로 2를 제외한 2의 배수(4,6,8...)를 제거
3. 3은 소수 → 3의 배수(6,9,12...)를 제거
4. 4는 이미 2의 배수로 제거되었으므로 skip
5. 5는 소수 → 5의 배수 제거
6. 6도 이미 제거됨 → 다음은 7의 배수 제거
7. ...
8. √144 = 12까지만 반복하면 됨

이렇게 하면 O(N log log N) 시간 복잡도로
N 이하의 모든 소수를 효율적으로 구할 수 있습니다.

---

💡 정리

에라토스테네스의 체는

• 범위가 큰 경우에서 모든 소수를 빠르게 구해야 하는 문제에서 매우 유용합니다.