에라토스테네스의 체 (Sieve of Eratosthenes)

정의

에라토스테네스의 체 (Sieve of Eratosthenes) 는 1부터 N 까지의 모든 소수를 O(N log log N) 에 찾는 고대 그리스 알고리즘. 기원전 240 년경 에라토스테네스가 고안. 선형 체 (Linear Sieve) 는 개선 버전으로 O(N) 에 모든 소수 + 최소 소인수 (SPF) 를 구한다.

문제 상황과 동기

N 이하의 모든 소수를 나열하라.

• naive: 각 수마다 소수 판정 O(√N) → 총 O(N√N). N=10^7 이면 10^10 연산.
• 에라토스테네스: 2 의 배수 지우기, 3 의 배수 지우기, … O(N log log N). N=10^7 도 0.1 초.
• 선형 체: 각 합성수를 최소 소인수로 정확히 한 번만 지움. O(N).

핵심 통찰: “소수 p 의 배수는 모두 합성수”. 작은 소수부터 배수를 지워 나가면 남은 수가 소수. 선형 체는 “각 합성수를 SPF 로만 지움” 으로 중복 제거.

자주 등장: 소인수분해, 오일러 φ, 뫼비우스 함수, 수론 DP (예: 약수 DP), 골드바흐 추측 검증.

시각화

핵심 아이디어

에라토스테네스 체

초기: is_prime[2..N] = true
for p = 2..√N:
    if is_prime[p]:
        for k = p^2, p^2 + p, ..., N:
            is_prime[k] = false

p^2 부터 시작: p * (p-1), p * (p-2), … 는 이미 더 작은 소수로 지워짐.

복잡도 분석: 각 소수 p 에 대해 N/p 번 지움. Σ (N/p) = N Σ (1/p) = N log log N (소수의 역수 합 → log log N).

선형 체 (Linear Sieve)

for i = 2..N:
    if spf[i] == 0:   # i 는 소수
        primes.append(i)
        spf[i] = i
    for p in primes:
        if i * p > N:
            break
        spf[i * p] = p
        if i % p == 0:
            break       # i 의 최소 소인수 = p, i*p 는 나중에 다시 안 지움

invariant: 각 합성수 n 은 SPF(n) 로만 지워진다. i % p == 0 일 때 break → 더 큰 p 는 i 의 진짜 소인수가 아님 → 중복 방지 → O(N).

알고리즘

에라토스테네스 체

sieve(N):
    is_prime[2..N] = true
    for p = 2..√N:
        if is_prime[p]:
            for k = p^2, p^2 + p, ..., N:
                is_prime[k] = false
    return [i for i in 2..N if is_prime[i]]

선형 체

linear_sieve(N):
    spf[2..N] = 0
    primes = []
    for i = 2..N:
        if spf[i] == 0:
            primes.append(i)
            spf[i] = i
        for p in primes:
            if i * p > N:
                break
            spf[i * p] = p
            if i % p == 0:
                break
    return primes, spf

구현

// 에라토스테네스 O(N log log N) + 선형 체 O(N)
#include <bits/stdc++.h>
using namespace std;
​
vector<int> sieve(int N) {
  vector<bool> is_prime(N + 1, true);
  is_prime[0] = is_prime[1] = false;
  for (int p = 2; p * p <= N; p++) {
      if (is_prime[p]) {
          for (int k = p * p; k <= N; k += p)
              is_prime[k] = false;
      }
  }
  vector<int> primes;
  for (int i = 2; i <= N; i++)
      if (is_prime[i]) primes.push_back(i);
  return primes;
}
​
pair<vector<int>, vector<int>> linear_sieve(int N) {
  vector<int> spf(N + 1, 0), primes;
  for (int i = 2; i <= N; i++) {
      if (spf[i] == 0) {
          primes.push_back(i);
          spf[i] = i;
      }
      for (int p : primes) {
          if (i * p > N) break;
          spf[i * p] = p;
          if (i % p == 0) break;
      }
  }
  return {primes, spf};
}
​
int main() {
  int N; cin >> N;
  auto primes1 = sieve(N);
  auto [primes2, spf] = linear_sieve(N);
  cout << "Eratosthenes: " << primes1.size() << " primes\n";
  cout << "Linear sieve: " << primes2.size() << " primes\n";
  cout << "First 10: ";
  for (int i = 0; i < min(10, (int)primes2.size()); i++)
      cout << primes2[i] << " ";
  cout << "\n";
}

# 에라토스테네스 O(N log log N) + 선형 체 O(N)
def sieve(N):
  is_prime = [True] * (N + 1)
  is_prime[0] = is_prime[1] = False
  for p in range(2, int(N**0.5) + 1):
      if is_prime[p]:
          for k in range(p * p, N + 1, p):
              is_prime[k] = False
  return [i for i in range(2, N + 1) if is_prime[i]]
​
def linear_sieve(N):
  spf = [0] * (N + 1)
  primes = []
  for i in range(2, N + 1):
      if spf[i] == 0:
          primes.append(i)
          spf[i] = i
      for p in primes:
          if i * p > N:
              break
          spf[i * p] = p
          if i % p == 0:
              break
  return primes, spf
​
N = int(input())
primes1 = sieve(N)
primes2, spf = linear_sieve(N)
print(f"Eratosthenes: {len(primes1)} primes")
print(f"Linear sieve: {len(primes2)} primes")
print("First 10:", *primes2[:10])

// 에라토스테네스 O(N log log N) + 선형 체 O(N)
import java.util.*;
public class Main {
  static List<Integer> sieve(int N) {
      boolean[] isPrime = new boolean[N + 1];
      Arrays.fill(isPrime, true);
      isPrime[0] = isPrime[1] = false;
      for (int p = 2; p * p <= N; p++) {
          if (isPrime[p]) {
              for (int k = p * p; k <= N; k += p)
                  isPrime[k] = false;
          }
      }
      List<Integer> primes = new ArrayList<>();
      for (int i = 2; i <= N; i++)
          if (isPrime[i]) primes.add(i);
      return primes;
  }
  static class Pair {
      List<Integer> primes;
      int[] spf;
      Pair(List<Integer> primes, int[] spf) { this.primes = primes; this.spf = spf; }
  }
  static Pair linearSieve(int N) {
      int[] spf = new int[N + 1];
      List<Integer> primes = new ArrayList<>();
      for (int i = 2; i <= N; i++) {
          if (spf[i] == 0) {
              primes.add(i);
              spf[i] = i;
          }
          for (int p : primes) {
              if (i * p > N) break;
              spf[i * p] = p;
              if (i % p == 0) break;
          }
      }
      return new Pair(primes, spf);
  }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int N = sc.nextInt();
      List<Integer> primes1 = sieve(N);
      Pair res = linearSieve(N);
      System.out.println("Eratosthenes: " + primes1.size() + " primes");
      System.out.println("Linear sieve: " + res.primes.size() + " primes");
      System.out.print("First 10: ");
      for (int i = 0; i < Math.min(10, res.primes.size()); i++)
          System.out.print(res.primes.get(i) + " ");
      System.out.println();
  }
}

100

Eratosthenes: 25 primes
Linear sieve: 25 primes
First 10: 2 3 5 7 11 13 17 19 23 29

10000

Eratosthenes: 1229 primes
Linear sieve: 1229 primes
First 10: 2 3 5 7 11 13 17 19 23 29

복잡도

에라토스테네스: N=10^7 일 때 ~0.05 초 (실전 충분). 선형 체: N=10^7 일 때 ~0.03 초. SPF 배열로 소인수분해도 O(log N).

변형 / 활용

1. 구간 체 (Segmented Sieve)

[L, R] (R-L ≤ 10^6, R ≤ 10^12) 의 소수 찾기. 작은 소수 (√R 이하) 만 미리 구함 → 구간 [L, R] 에서 배수 지움. O(√R + (R-L) log log R).

2. 소인수분해 O(log N)

선형 체로 SPF[n] 알면 n = SPF[n] · (n / SPF[n]) 재귀. log N 회.

vector<int> factorize(int n, const vector<int>& spf) {
    vector<int> factors;
    while (n > 1) {
        factors.push_back(spf[n]);
        n /= spf[n];
    }
    return factors;
}

3. 오일러 φ 함수

φ(n) = n · Π (1 - 1/p) (p: n 의 소인수). 선형 체로 모든 φ(1..N) 을 O(N) 에.

4. 뫼비우스 함수 μ(n)

μ(n) = (-1)^k (k: 서로 다른 소인수 개수), 제곱 인수 있으면 0. 포함-배제.

함정

1. 범위 시작

is_prime[0], is_prime[1] 을 false 로 초기화 안 하면 오답.

2. p^2 overflow

p * p 가 int 범위 넘으면 오버플로우. p * p > N 대신 p > sqrt(N) 또는 long long.

3. 선형 체 break 조건

if (i % p == 0) break 빼먹으면 O(N^2) 로 폭발. 핵심 invariant.

4. 메모리

N=10^8 이면 bool 배열 100MB. 비트셋으로 압축 가능.

BOJ 연습 문제

참고

• 정수론
• 소인수분해
• 밀러-라빈 소수 판정
• 오일러 파이 함수