핵심 인사이트

  1. 에라토스테네스의 체(Sieve of Eratosthenes)는 2~N까지 소수를 한 번에 구하는 O(N log log N) 알고리즘 — "소수의 배수를 모두 제거"하는 원리로, N이 클 때 개별 소수 판별을 N번 반복하는 O(N√N)보다 압도적으로 효율적이다.
  2. 배수 제거 시작점이 p² — 소수 p의 배수를 제거할 때 2p, 3p, ...(p-1)p는 이미 앞선 소수에 의해 제거됐으므로, p²부터 시작하면 불필요한 연산을 줄일 수 있다.
  3. 비트 배열과 분할 체로 메모리와 캐시 효율을 극대화 — N=10억 범위의 소수 구하기는 Segmented Sieve로 분할하여 L1 캐시 크기에 맞춰 처리해야 실용적이다.

Ⅰ. 알고리즘 원리

에라토스테네스의 체 동작 원리:

1단계: 2부터 N까지 배열 생성
  [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...]

2단계: 소수 p=2 → p²부터 p 배수 제거
  제거: 4, 6, 8, 10, 12, ...
  [2, 3, _, 5, _, 7, _, 9, _, 11, _, 13, ...]

3단계: 다음 소수 p=3 → p²=9부터 3 배수 제거
  (6은 이미 제거, 9부터)
  제거: 9, 12, 15, ...

4단계: p=5 → 25부터 제거
  (10, 15, 20은 이미 제거)

5단계: p > √N이면 종료
  (이후 소수의 배수는 이미 모두 제거됨)

예: 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 제거
  p=3: 9,15,21,27 제거 (6,12...는 이미 제거)
  p=5: 25 제거 (10,15,20,30은 이미 제거)
  p=7 > √30≈5.47이므로 종료
  
  결과: [2,3,5,7,11,13,17,19,23,29]

왜 p²부터 시작?
  소수 p를 처리할 때:
  2p, 3p, ..., (p-1)p는 모두 2, 3, ..., p-1 중 소수의 배수
  → 이미 이전 단계에서 제거됨
  → p²부터 처리하면 됨

📢 섹션 요약 비유: 에라토스테네스의 체 = 번호표 소각 — 2번 배수(짝수) 소각, 3번 배수 소각, 5번 배수 소각... 남은 번호표가 모두 소수! 불필요한 것을 제거하는 소수 대청소!

Ⅱ. 구현

# 기본 구현 O(N log log N)
def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0, 1은 소수 아님
    
    p = 2
    while p * p <= n:  # p <= √n
        if is_prime[p]:
            # p² 부터 p 배수 제거
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
        p += 1
    
    return [i for i in range(2, n + 1) if is_prime[i]]

# 테스트
primes = sieve_of_eratosthenes(30)
print(primes)  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

primes_100 = sieve_of_eratosthenes(100)
print(len(primes_100))  # 25 (100 이하 소수 25개)

# 성능 비교
# N = 1,000,000
# 개별 판별 O(N√N): 약 10^9 연산
# 에라토스테네스 O(N log log N): 약 3.8×10^6 연산
# → 263배 빠름

# 비트 배열 최적화 (메모리 8배 절감)
def sieve_bitarray(n):
    from bitarray import bitarray
    is_prime = bitarray(n + 1)
    is_prime.setall(True)
    is_prime[0] = is_prime[1] = False
    
    p = 2
    while p * p <= n:
        if is_prime[p]:
            is_prime[p*p::p] = False  # 슬라이스 연산
        p += 1
    
    return [i for i in range(2, n+1) if is_prime[i]]

메모리 사용량:

N = 10,000,000 (천만)
bool 배열: 10MB
비트 배열: 1.25MB (8배 절감)

N = 1,000,000,000 (10억)
bool 배열: 1GB (불가)
비트 배열: 125MB (가능)
Segmented Sieve: L1 캐시 크기(32KB)로 분할

📢 섹션 요약 비유: 체 구현 — is_prime 배열에서 배수 제거. N=100만에서 개별 판별보다 263배 빠름. 비트 배열로 메모리도 8배 절감!

Ⅲ. 분할 체 (Segmented Sieve)

Segmented Sieve:
  대용량 N(10억~)을 작은 세그먼트로 분할
  L1 캐시(32KB)에 맞춰 처리

알고리즘:
  1. √N까지의 소수를 기본 체로 구함
  2. N을 세그먼트 크기(seg_size)로 분할
  3. 각 세그먼트에 기본 소수의 배수 표시

세그먼트 크기 = min(√N, 캐시 크기에 맞는 크기)

```python
import math

def segmented_sieve(n):
    limit = int(math.sqrt(n)) + 1
    # 기본 소수 (√N까지)
    base_primes = sieve_of_eratosthenes(limit)
    
    primes = list(base_primes)
    
    # 세그먼트 처리
    seg_size = limit
    low = limit + 1
    
    while low <= n:
        high = min(low + seg_size - 1, n)
        sieve = [True] * (high - low + 1)
        
        for p in base_primes:
            # 세그먼트 내 p의 첫 배수 위치
            start = ((low + p - 1) // p) * p
            if start == p:
                start += p  # p 자신은 제외
            
            for j in range(start, high + 1, p):
                sieve[j - low] = False
        
        for i in range(len(sieve)):
            if sieve[i]:
                primes.append(low + i)
        
        low = high + 1
    
    return primes

참고로 10억 이하의 소수 개수는 50,847,534개이며, 이는 소수 정리 (Prime Number Theorem)의 근사값 n / ln(n)와 비슷한 수준이다.

장점: 캐시 친화적 (세그먼트가 L1 캐시에 들어감) 메모리 효율적 (전체 배열 불필요)

성능: N = 10억: 기본 체: 1GB 메모리 필요 분할 체: 32KB × 반복 = 32KB만 필요 속도: 3~5배 빠름 (캐시 효율)


> 📢 **섹션 요약 비유**: 분할 체 = 큰 교실을 작은 그룹으로 — 1000명 전체(10억) 한 번에 처리 불가. 30명씩 그룹(세그먼트)으로 나눠서 체 처리. 책상(캐시)에 다 올라오는 크기로!

---

## Ⅳ. 소수 정리와 응용

소수 정리 (Prime Number Theorem): N 이하 소수 개수 π(N) ≈ N / ln(N)

π(100) = 25 (실제) vs 100/ln(100) ≈ 21.7 π(1,000,000) = 78,498 vs 10^6/ln(10^6) ≈ 72,382 N이 클수록 근사 정확도 향상

소수 관련 개념: 쌍둥이 소수 (Twin Primes): (3,5), (5,7), (11,13), (17,19), ... 차이 = 2인 소수 쌍, 무한히 많은지 미증명 (추측)

메르센 소수: 2^n - 1 형태 소수 M(2)=3, M(3)=7, M(5)=31, M(7)=127 현재 알려진 최대 소수: 2^82,589,933 - 1 (2018)

응용:

  1. 암호학: RSA: 큰 소수 p, q 생성 (512~4096 비트) 에라토스테네스 체로 소수 후보 필터 후 밀러-라빈 테스트로 확인

  2. 해시 테이블: 크기를 소수로 설정 → 해시 충돌 감소

  3. 코딩테스트: "N까지 소수의 합" → 에라토스테네스 O(N log log N) "N이 소수인지" → 밀러-라빈 O(k log²N) "소인수분해" → 폴라드 로 알고리즘

  4. 정수론 문제: GCD + 소수 = 정수론 알고리즘의 핵심


> 📢 **섹션 요약 비유**: 소수 응용 — RSA 암호는 큰 소수(비밀번호), 해시 테이블은 소수 크기(충돌 방지), 코딩테스트는 체 알고리즘(빠른 계산). 수학이 현대 컴퓨팅을 지탱!

---

## Ⅴ. 실무 시나리오 — 암호화 소수 생성

시나리오: RSA 키 생성에서 소수 판별

목표: 512비트 소수 p, q 생성 (RSA-1024) (10^154 범위의 소수)

과정:

  1. 에라토스테네스 체로 작은 소수 목록 생성 (100,000 이하) 이유: 큰 난수가 작은 소수로 나뉘는지 빠르게 검사

  2. 난수 n (512비트) 생성 홀수로 만들기 (짝수는 소수 불가: n | 1)

  3. 작은 소수 테스트: for p in small_primes: if n % p == 0: 버리고 다음 난수

    속도: n이 합성수일 확률 ~70% 빠르게 걸러냄

  4. 밀러-라빈 확률 소수 테스트: k=15 라운드 → 오류 확률 < 4^(-15) ≈ 10^(-9)

  5. 통과하면 소수로 채택

통계: 512비트 소수 밀도: 약 1/ln(2^512) ≈ 1/355 평균 355번 난수 생성하면 소수 1개

에라토스테네스의 역할: 1단계 빠른 필터 역할 100,000 이하 소수: 9,592개 (30밀리초 생성) 큰 합성수 ~70% 제거 → 밀러-라빈 부담 감소

성능: 에라토스테네스 없이: 355번 × 밀러-라빈 시간 에라토스테네스 포함: 355번 × (빠른 체크 + 0.3 × 밀러-라빈) → 3배 빠름


> 📢 **섹션 요약 비유**: 소수 생성 파이프라인 — 에라토스테네스(초등 검문소: 70% 걸러냄) + 밀러-라빈(전문 검사: 나머지 확인). 두 단계 협력으로 RSA 소수 효율적 생성!

---

## 📌 관련 개념 맵

에라토스테네스의 체 +-- 핵심 원리: 배수 제거 +-- 최적화 | +-- p²부터 시작 | +-- 비트 배열 | +-- Segmented Sieve +-- 복잡도: O(N log log N) +-- 응용 | +-- RSA 소수 생성 | +-- 해시 테이블 크기 | +-- 코딩테스트 소수 문제 +-- 관련 개념 +-- 밀러-라빈 소수 테스트 +-- 소수 정리 (π(N) ≈ N/ln N)


---

## 📈 관련 키워드 및 발전 흐름도

[에라토스테네스 (기원전 240년)] 알렉산드리아 도서관장 손으로 계산한 소수 체 | v [소수 정리 (1896)] 아다마르, 발레 푸생 π(N) ≈ N/ln(N) 증명 | v [밀러-라빈 테스트 (1980)] 확률 소수 판별 대용량 소수 생성 | v [Segmented Sieve (1987)] 캐시 최적화 10억 이상 범위 | v [현재: 양자 시대 위협] 쇼어 알고리즘: 소수 기반 RSA 해독 Post-Quantum 암호로 전환 중


---

## 👶 어린이를 위한 3줄 비유 설명

1. 에라토스테네스의 체 = 번호표 소각 — 2번 배수 다 소각, 3번 배수 소각... 남은 번호표가 소수! 배수를 지우는 대청소!
2. p²부터 시작 = 이미 한 청소 반복 안 하기 — 3의 배수 중 6은 이미 2가 청소했어요. 9부터(3²) 시작하면 더 효율적!
3. Segmented Sieve = 큰 책 쪽 나눠 읽기 — 1000페이지 책을 30페이지씩 나눠 읽으면 책상(캐시)에 올라가요. 10억도 빠르게 처리!