에라토스테네스의 체

N 이하의 소수를 한 번에 구하는 알고리즘으로, 소수의 배수를 반복적으로 지워 나가는 방식입니다.

핵심 아이디어

소수 p를 찾으면 p의 배수는 모두 합성수이므로 제거합니다.

[ N = 30, 소수 찾기 ]

초기: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

p=2: 4 6 8 10 12 14 16 18 20 22 24 26 28 30 제거
     2 3 5 7 9 11 13 15 17 19 21 23 25 27 29

p=3: 9 15 21 27 제거  (6 12 18 24 30은 이미 제거됨)
     2 3 5 7 11 13 17 19 23 25 29

p=5: 25 제거  (10 15 20 30은 이미 제거됨)
     2 3 5 7 11 13 17 19 23 29

p=7: 7² = 49 > 30 → 중단

결과 소수: 2 3 5 7 11 13 17 19 23 29

구현

boolean[] sieve(int n) {
    boolean[] isComposite = new boolean[n + 1];  // false = 소수
    isComposite[0] = isComposite[1] = true;

    for (int i = 2; (long) i * i <= n; i++) {
        if (!isComposite[i]) {
            for (int j = i * i; j <= n; j += i) {
                isComposite[j] = true;
            }
        }
    }
    return isComposite;
}

핵심 최적화 2가지

① 외부 루프를 √N까지만

N의 합성수는 반드시 √N 이하의 소인수를 가집니다.
→ i > √N이면 i의 배수는 이미 더 작은 소수에 의해 제거됨
→ i * i <= n 조건으로 중단

② 내부 루프를 i²에서 시작

p = 5일 때:
  5 × 2 = 10 → p=2 단계에서 이미 제거
  5 × 3 = 15 → p=3 단계에서 이미 제거
  5 × 4 = 20 → p=2 단계에서 이미 제거
  5 × 5 = 25 → ← 여기서부터 새로 제거 필요

→ j = i * i 에서 시작하면 중복 작업 없음

i * i 계산 시 int 범위 초과 가능 — (long) i * i <= n 으로 캐스팅 필수

시간복잡도

단계복잡도
전체O(n log log n)
단순 소수 판별 (1개)O(√n)
n개 소수 판별 (체 없이 반복)O(n√n)
 
체의 작업량 = n/2 + n/3 + n/5 + n/7 + ...
           ≈ n × Σ(1/p)   (소수 p에 대한 합)
           ≈ n × log log n    (소수 역수 합의 점근식)

n = 10⁶: 약 2천만 연산 / n = 10⁷: 약 2.3천만 연산 — 실용적으로 거의 선형

소수 목록 추출

// 체 결과에서 소수 리스트 만들기
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
    if (!isComposite[i]) primes.add(i);
}

구간 소수 (Segmented Sieve)

N이 매우 크지만 [L, R] 범위만 필요할 때. 전체 배열을 만들기 어려운 경우 사용.

// 아이디어: √R 이하의 소수로 [L, R] 범위만 체질
boolean[] segSieve(long L, long R) {
    int sqrtR = (int) Math.sqrt(R);
    boolean[] smallComp = sieve(sqrtR);  // √R 이하 소수 구하기

    boolean[] isComp = new boolean[(int)(R - L + 1)];  // [L, R] 범위

    for (int p = 2; p <= sqrtR; p++) {
        if (!smallComp[p]) {
            long start = Math.max((long) p * p, ((L + p - 1) / p) * p);
            for (long j = start; j <= R; j += p) {
                isComp[(int)(j - L)] = true;
            }
        }
    }
    if (L == 1) isComp[0] = true;  // 1은 소수 아님
    return isComp;
}

단일 소수 판별 vs 에라토스테네스의 체

상황선택이유
소수 1개 판별단일 판별 O(√n)체 초기화 비용이 더 큼
N 이하 소수 전부에라토스테네스의 체O(n log log n)
소수 판별을 여러 번에라토스테네스의 체 미리 계산이후 조회 O(1)
매우 큰 N, 좁은 구간구간 체메모리 절약

단일 소수 판별

boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; (long) i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

주의사항

배열 크기

// N = 10^6이면
boolean[] isComposite = new boolean[1_000_001];  // N+1 크기 필요

// 자주 하는 실수: N 선언 후 N+1 크기 잊기
int N = 1_000_000;
boolean[] arr = new boolean[N];    // X arr[N] 접근 시 IndexOutOfBounds
boolean[] arr = new boolean[N+1];  // O

1과 0 처리

isComposite[0] = isComposite[1] = true;  // 0, 1은 소수 아님

i * i 오버플로

// i = 50,000, i*i = 2,500,000,000 → int 최대값(2,147,483,647) 초과
for (int i = 2; i * i <= n; i++)          // X 오버플로 가능
for (int i = 2; (long) i * i <= n; i++)   // O

핵심 정리

CSLOG에서 보기