에라토스테네스의 체란? (소수 구하기 알고리즘 정리)

1. 에라토스테네스의 체란?

에라토스테네스의 체(Sieve of Eratosthenes)는
1부터 N까지의 모든 소수를 한 번에 구하는 알고리즘이다.

소수를 하나하나 판별하는 방식이 아니라,
👉 소수가 아닌 수를 미리 제거하는 방식이라는 점이 핵심이다.

---

2. 왜 필요한가?

예를 들어 다음과 같은 문제가 있다고 하자.

M 이상 N 이하의 모든 소수를 출력하라
(N ≤ 1,000,000)

이때 각 수마다 √N까지 나누어보는 방식으로 소수를 판별하면
연산량이 너무 많아 시간 초과가 발생할 수 있다.

이럴 때 사용하는 것이 에라토스테네스의 체다.

---

3. 핵심 아이디어

1. 2는 소수 → 2의 배수는 전부 소수가 아님
2. 다음 남은 수 3 → 3의 배수 제거
3. 다음 남은 수 5 → 5의 배수 제거
4. 이 과정을 √N까지만 반복

이렇게 하면 소수가 아닌 수는 모두 제거되고,
남아 있는 수들만 소수가 된다.

👉 “소수인지 묻지 말고, 소수가 아닌 걸 지운다”

---

4. 왜 √N까지만 반복하나?

어떤 수 x가 합성수라면
x = a × b 형태로 나타낼 수 있다.

이때 두 수 모두 √x보다 클 수는 없다.
→ 최소 하나는 √x 이하

그래서 √N까지만 검사해도
그 이후의 합성수는 이미 이전 단계에서 제거된다.

---

5. 예시로 이해하기 (N = 20)

초기 상태

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

• 2의 배수 제거
• 3의 배수 제거
• 5의 배수 제거

남은 수:

2 3 5 7 11 13 17 19

---

6. 자바 구현 코드

import java.util.Scanner;

public class Main {

    static public boolean isPrime(int a){
        if (a == 2) return true;
        if (a == 1 || a % 2 == 0) return false;
        for(int i = 3; i * i <= a; i+=2){
            if(a % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();

        for (int i = M; i <= N; i++) {
            if (isPrime(i)) {
                System.out.println(i);
            }
        }
    }
}

---

7. j = i * i부터 시작하는 이유

i × 2, i × 3, … 같은 값들은
이미 더 작은 소수 단계에서 제거되었기 때문이다.

예:

• 6 = 2 × 3 → 2 단계에서 제거됨
• 9 = 3 × 3 → 3 단계에서 처음 등장

👉 중복 제거를 막기 위한 중요한 최적화

---

8. 시간복잡도

• O(N log log N)
• 체감상 거의 O(N)

범위 전체의 소수를 구할 때
가장 빠르고 안정적인 방법이다.

---

9. 언제 사용해야 할까?

• ✅ 범위 내 모든 소수 출력
• ✅ N이 크다 (백만 이상)
• ❌ 소수 하나만 판별하는 문제에는 과함

---

10. 정리

• 에라토스테네스의 체는 범위형 소수 문제의 정석
• 개별 판별보다 훨씬 빠르고 안정적
• 코딩 테스트에서 자주 등장하는 핵심 알고리즘

👉 “범위 전체의 소수 = 에라토스테네스”

---