에라토스테네스의 체

에라토스테네스의 체란?

하나의 수가 소수인지 판정하는 것은 \(O(\sqrt N)\)이면 됩니다. 하지만 \(1\)부터 \(N\)
까지의 모든 소수가 필요하다면, 각 수를 따로 판정하면 \(O(N \sqrt N)\)으로 느립니다.

에라토스테네스의 체(Sieve of Eratosthenes) 는 이 문제를 거의 \(O(N)\)에 가깝게
푸는 고전 알고리즘입니다. 핵심 발상은 단순합니다 — 소수를 찾기보다, 합성수를
지운다.

1. 동작 원리

\(2\)부터 시작해, 어떤 수가 아직 지워지지 않았다면 그것은 소수입니다. 그 소수의
배수들을 전부 지웁니다. 다음 안 지워진 수로 넘어가 반복합니다.

2 3 4 5 6 7 8 9 10 11 12 ...
2의 배수 지움: 4 6 8 10 12 지움
3의 배수 지움: 9 12(이미) 지움
5의 배수 지움: 10(이미) ...
남은 것: 2 3 5 7 11 ... → 소수!

"한 수가 소수냐"를 묻는 대신 "소수의 배수를 일괄 제거"하는 것이 핵심 전환입니다.

2. 왜 빠른가: 복잡도

배수를 지우는 총 횟수는

$$ \frac{N}{2} + \frac{N}{3} + \frac{N}{5} + \cdots = N \sum_{p \le N} \frac{1}{p} $$

이 조화급수(소수에 대한)는 \(\ln \ln N\)으로 수렴해, 전체 복잡도가
\(O(N \log \log N)\)입니다. \(\log \log N\)은 사실상 작은 상수에 가까워, 실용적으로
거의 선형입니다. \(N = 10^7\)까지도 순식간에 처리됩니다.

3. 핵심 최적화 두 가지

체를 짤 때 두 가지 최적화를 반드시 기억하세요.

• \(\sqrt N\)까지만 거르기: \(i > \sqrt N\)인 소수의 배수는 이미 더 작은 소인수에
  의해 지워졌습니다. 그래서 바깥 반복은 \(i \le \sqrt N\)까지만.
• \(i \times i\)부터 지우기: \(i\)의 배수 중 \(2i, 3i, \dots, (i{-}1)i\)는 더 작은
  소수가 이미 지웠습니다. 그래서 \(i^2\)부터 시작합니다.

이 두 가지를 빠뜨려도 답은 맞지만, 넣으면 눈에 띄게 빨라집니다.

4. 체가 주는 부가 정보

체는 소수 목록만 주지 않습니다. 살짝 바꾸면 더 많은 걸 얻습니다.

특히 빠른 소인수분해가 강력합니다. 각 수의 가장 작은 소인수를 미리 체로
구해 두면, 어떤 수든 \(O(\log N)\)에 소인수분해할 수 있습니다.

5. 언제 쓰나

• 여러 수의 소수 여부를 반복해서 물어볼 때.
• 어떤 범위의 소수를 모두 나열해야 할 때.
• 많은 수를 빠르게 소인수분해해야 할 때.

반대로 수 하나만 판정한다면 \(O(\sqrt N)\) 시도 나눗셈이 더 간단합니다.

정리

체는 "소수를 찾는다"가 아니라 "합성수를 지운다"는 발상의 전환입니다.
\(O(N \log \log N)\)에 범위 내 모든 소수를 얻고, 약간 변형하면 빠른 소인수분해까지
공짜로 따라옵니다.

체를 코드로

기본 체, 최적화, 그리고 가장 유용한 응용인 빠른 소인수분해를 구현합니다.

1. 기본 체 (불리언 배열)

const int N = 1000000;
bool composite[N + 1];               // true면 합성수

void sieve() {
    for (int i = 2; (long long)i * i <= N; i++)   // sqrt(N)까지
        if (!composite[i])                        // i가 소수면
            for (int j = i * i; j <= N; j += i)    // i*i부터 배수 지움
                composite[j] = true;
}
// 사용: composite[x] == false 이고 x >= 2 이면 소수

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= n:                 # sqrt(n)까지
        if is_prime[i]:
            for j in range(i * i, n + 1, i):   # i*i부터
                is_prime[j] = False
        i += 1
    return is_prime

i * i부터, 바깥은 \(\sqrt N\)까지 — 두 최적화를 모두 적용했습니다.

2. 소수 목록 뽑기

vector<int> primes;
for (int i = 2; i <= N; i++)
    if (!composite[i]) primes.push_back(i);

primes = [i for i in range(2, n + 1) if is_prime[i]]

3. 최소 소인수 체 → 빠른 소인수분해

각 수의 가장 작은 소인수(smallest prime factor, spf) 를 체로 기록해 두면,
어떤 수든 \(O(\log N)\)에 소인수분해됩니다.

int spf[N + 1];                      // spf[x] = x의 최소 소인수
void buildSpf() {
    for (int i = 2; i <= N; i++) {
        if (spf[i] == 0)             // 아직 안 채워졌으면 i는 소수
            for (int j = i; j <= N; j += i)
                if (spf[j] == 0) spf[j] = i;
    }
}
vector<int> factorize(int x) {
    vector<int> f;
    while (x > 1) { f.push_back(spf[x]); x /= spf[x]; }
    return f;                        // 소인수들 (중복 포함)
}

def build_spf(n):
    spf = list(range(n + 1))         # spf[x] 초기값 = x
    i = 2
    while i * i <= n:
        if spf[i] == i:              # i가 소수
            for j in range(i * i, n + 1, i):
                if spf[j] == j:
                    spf[j] = i
        i += 1
    return spf

def factorize(x, spf):
    f = []
    while x > 1:
        f.append(spf[x])
        x //= spf[x]
    return f

factorize(360)은 [2, 2, 2, 3, 3, 5]를 돌려줍니다. 매번 \(\sqrt x\)로 나누는
것보다 훨씬 빠릅니다.

4. 메모리 주의

체는 \(N + 1\) 크기의 배열이 필요합니다. \(N = 10^8\)이면 불리언 배열만 100MB라
메모리 제한에 걸릴 수 있습니다. 이럴 땐 비트 압축(8개를 1바이트에)이나
홀수만 저장하는 기법을 씁니다. 보통 \(N \le 10^7\)이면 평범한 배열로 충분합니다.

5. 흔한 실수

• i * i 오버플로 — N이 크면 i * i가 int를 넘칩니다. (long long)i * i로.
• 0, 1 처리 — \(0\)과 \(1\)은 소수가 아닙니다. 따로 표시하세요.
• 메모리 초과 — \(N\)이 \(10^8\)급이면 압축을 고려.
• 시작 인덱스 — 안쪽 반복을 2*i가 아니라 i*i부터 하는 게 표준 최적화.

6. 패턴 알아보기

• "\(N\)까지 소수를 모두" / "여러 번 소수 판정" → 체.
• "많은 수를 소인수분해" → 최소 소인수 체.
• "수 하나만 판정" → 그냥 \(O(\sqrt N)\) 시도 나눗셈.

실전에서 체 문제 알아보기

소수가 나온다고 전부 체는 아닙니다. "몇 개의 수를, 어느 범위에서, 몇 번
판정하는가" 에 따라 도구가 갈립니다. 그 판단 기준을 정리합니다.

1. 출제 신호

• "\(N\) 이하의 모든 소수", "범위 \([A, B]\)의 소수" — 범위 전체가 대상이면
  체가 정답입니다. 보통 \(N \le 10^6 \sim 10^7\)로 출제됩니다.
• 소수 판정 질의가 여러 번 — 골드바흐(짝수 = 소수 + 소수), 소수 쌍 찾기.
  체로 is_prime 표를 한 번 만들면 질의당 \(O(1)\)입니다.
• 여러 수의 소인수분해 — 최소 소인수(SPF) 체를 만들면 각 수를
  \(O(\log N)\)에 분해합니다.
• 반대로 수가 한두 개뿐이고 큰 경우(\(10^{12}\) 등)는 체가 아니라
  \(O(\sqrt{N})\) 시험 나눗셈입니다.

2. 풀이 결정 절차

1. 판정 대상이 몇 개인가? — 한두 개면 \(\sqrt{N}\) 판정, 범위 전체나
   다수 질의면 체.
2. 범위 상한을 확인합니다 — \(10^7\)이면 bool 배열 약 10MB로 가능,
   그 이상이면 메모리부터 계산하세요.
3. 소수 목록만 필요한가, 소인수분해도 필요한가? — 후자라면 처음부터
   SPF 체를 만드는 편이 깔끔합니다.
4. 체를 만든 뒤 본 문제(쌍 찾기, 구간 세기 등)는 누적 합·투 포인터 같은
   별도 기법과 결합되는 경우가 많습니다.

3. 자주 하는 실수

• 1을 소수로 처리. 체 배열을 전부 true로 초기화한 뒤 0과 1을 끄는 것을
  잊으면 골드바흐류에서 오답이 납니다.
• 안쪽 시작점. \(i\)의 배수 지우기는 \(i \times i\)부터 시작해도 충분합니다
  (그보다 작은 배수는 이미 더 작은 소수가 지움). \(i \times i\)가 int 범위를
  넘을 수 있으니 곱셈 타입에 주의하세요.

vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;            // 0, 1 제외 필수
for (long long i = 2; i * i <= n; i++)        // i*i 오버플로 방지
    if (is_prime[i])
        for (long long j = i * i; j <= n; j += i)
            is_prime[j] = false;

• 파이썬에서 이중 루프 체. 순수 파이썬 루프는 \(10^7\)에서 너무 느립니다.
  슬라이스 대입 sieve[i*i::i] = [False] * len(...) 패턴으로 내부 루프를
  C 수준으로 내리세요.
• 매 테스트케이스마다 체를 다시 만듦. 체는 한 번만 만들고 모든 질의가
  공유해야 합니다.
• 메모리 초과. int 배열 대신 bool/bytearray를 쓰면 메모리가 ¼
  이하로 줄어듭니다.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 순으로 정렬되어 있습니다. 단순 범위
소수 출력에서 시작해, 체 + 누적 합, 체 + 투 포인터로 결합되는 문제까지
순서대로 올라가세요.

각 문제에서 "체로 만들 표가 무엇인지(소수 여부? 개수 누적? 최소 소인수?)"를
먼저 정하고 코딩하세요. 3문제 이상 풀어 클리어하면 레이팅의
CLASS 보너스에 반영됩니다.