algo · 18

에라토스테네스의 체

수학에라토스테네스소수

에라토스테네스의 체(sieve of Eratosthenes)는 2부터 시작해 소수의 배수를 차례로 지워 나가며 n 이하의 소수를 한꺼번에 찾는 알고리즘입니다. 지워지지 않고 끝까지 남은 수가 소수입니다. 수 하나하나를 나눠 보지 않고 배수만 건너뛰며 지우므로 나눗셈이 필요 없습니다.

시간은 O(n log log n)으로 선형에 매우 가깝고, 공간은 n 크기의 배열 O(n)입니다. 이 토픽에서는 50 이하의 수로 체가 걸러내는 과정과 p² 부터 지우는 이유, 그리고 n을 키울 때 지우는 횟수가 얼마나 늘어나는지를 직접 확인합니다.

핵심 개념

배수 지우기

2부터 지워지지 않은 가장 작은 수를 소수로 확정하고, 그 수의 배수를 모두 지웁니다. 이를 반복하면 남은 수가 소수입니다.

핵심 개념

p²부터 시작

p × k에서 k가 p보다 작으면 k의 소인수가 이미 그 배수를 지웠습니다. 그래서 p의 배수는 p × p부터 지우면 충분합니다.

핵심 개념

√n까지만

합성수는 자신의 제곱근 이하의 소인수를 가집니다. 그래서 p × p가 n 이하인 소수 p까지만 처리하면 n 이하의 합성수가 모두 지워집니다.

핵심 개념

소수 표 한 번에

한 수의 소수 여부가 아니라 n 이하 모든 수의 소수 여부를 배열로 얻습니다. 이후 판정은 배열을 읽는 O(1)입니다.

핵심 개념

O(n log log n)

소수 p마다 약 n/p칸을 지우고, 소수의 역수의 합이 log log n처럼 아주 천천히 자라므로 전체가 n log log n에 가깝습니다.

핵심 개념

공간 O(n)

n + 1칸의 배열이 필요합니다. n이 매우 크면 비트 하나에 수 하나를 담거나 구간을 나눠 처리해 메모리를 줄입니다.

시간은 O(n log log n)입니다 — 지우는 횟수의 합이 n × (1/2 + 1/3 + 1/5 + ...)에 가깝고, √n 이하의 소수만 다루므로 실제로는 n에 조금 더 곱해진 정도입니다.

공간은 O(n)입니다 — 각 수가 지워졌는지를 기록하는 배열이 필요합니다. 한 칸이 바이트 하나이면 n = 10,000,000일 때 약 10MB입니다.

한 수만 판정할 때는 알맞지 않습니다 — 큰 수 하나의 소수 여부는 √n까지 나눠 보는 시험 나눗셈이 훨씬 가볍습니다. 체는 범위 전체의 표가 필요할 때 씁니다.

같은 칸을 여러 번 지웁니다 — 12는 2와 3이 모두 접근합니다. 앞선 소수가 이미 지운 칸도 접근 횟수에 포함되며, 이 중복이 로그 로그 항으로 이어집니다.

이 시각화에서 확인할 것 — "체 걸러내기" 탭에서 p = 2, 3, 5, 7이 차례로 배수를 지우고 남은 15개가 소수로 확정되는 모습을, "p²부터 지우는 이유" 탭에서 5의 배수 10, 15, 20이 이미 지워져 있어 25부터 지우는 모습을, "n이 커지면" 탭에서 n당 지우는 횟수가 천천히만 늘어나는 모습을 STEP으로 확인하세요.

에라토스테네스의 체의 배경

이 방법은 고대 그리스의 수학자 키레네의 에라토스테네스(Eratosthenes of Cyrene)에게서 이름을 얻었습니다. 그의 저작 대부분은 전해지지 않고, 체는 이후 니코마코스(Nicomachus of Gerasa)의 『산술 입문』에서 그의 방법으로 소개됩니다. 소수의 배수를 지워 가는 방식 자체는 오늘날에도 같은 구조로 쓰입니다.

시간 복잡도에 나오는 log log n은 소수의 역수의 합과 관련이 있습니다. 메르텐스의 정리(Mertens' theorems)에 따르면 x 이하의 소수 p에 대한 1/p의 합은 ln ln x에 상수를 더한 값에 가깝게 자랍니다. 체를 개선한 알고리즘도 있습니다. 1978년 Gries와 Misra는 정수 곱셈을 단위 시간으로 볼 때 n에 비례하는 시간에 동작하는 선형 체를 발표했습니다. 이 방식은 합성수를 한 번씩만 지우는 구조로 알려져 있습니다.

숫자로 확인하기

50 이하의 소수 — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47로 모두 15개입니다. 처리한 소수는 2, 3, 5, 7뿐이고 다음 소수 11의 제곱 121이 50보다 커서 멈춥니다.

소수별 지우기 — p = 2는 4부터 24칸, p = 3은 9부터 14칸, p = 5는 25부터 6칸, p = 7은 49 한 칸에 접근해 모두 45번입니다. 새로 지운 수는 24개, 7개, 2개, 1개로 34개이며 2 이상 50 이하의 합성수 개수와 같습니다.

p²부터 지우는 이유 — 5의 배수 10, 15, 20은 각각 2, 3, 2가 이미 지웠고 25가 처음입니다. 5가 새로 지운 수는 25와 35 두 개입니다.

n을 키웠을 때 — n = 100, 1,000, 10,000, 100,000, 1,000,000에서 접근 횟수는 104, 1,411, 16,981, 193,078, 2,122,048번이고 n당 1.04, 1.41, 1.70, 1.93, 2.12입니다. 소수는 25, 168, 1,229, 9,592, 78,498개입니다.

코드 확인 — 파이썬과 자바가 50 이하에서 같은 15개 소수를 내고, 두 언어 모두 n = 1,000,000 이하의 소수를 78,498개로 셉니다.

자주 하는 오해

모든 수의 배수를 지워야 한다 — 소수의 배수만 지우면 됩니다. 합성수의 배수는 그 합성수의 소인수가 이미 지웠습니다.

p × 2부터 지워야 한다 — p × k에서 k가 p보다 작으면 k의 소인수가 이미 지웠으므로 p × p부터 시작해도 결과가 같고 접근 횟수만 줄어듭니다.

바깥 반복을 n까지 돌려야 한다 — p × p가 n을 넘으면 지울 것이 없으므로 √n까지만 돌면 됩니다. 이후 남은 수는 확인 없이 소수입니다.

시간이 O(n²)이다 — 겉으로는 이중 반복이지만 소수 p마다 n/p칸만 지우므로 합이 n log log n 정도입니다. n = 1,000,000에서도 접근은 약 212만 번입니다.

수 하나의 소수 판정에도 좋다 — 한 수의 소수 여부만 알면 되면 √n까지 나눠 보는 쪽이 메모리도 시간도 적게 듭니다. 체는 범위 전체가 필요할 때 이득입니다.

면접에서 이렇게 물어요

면접 질문

에라토스테네스의 체의 원리는?

2부터 지워지지 않은 가장 작은 수를 소수로 확정하고 그 배수를 지우는 일을 반복합니다. 끝까지 남은 수가 소수입니다.

면접 질문

왜 √n까지만 확인하면 되나요?

n 이하의 합성수는 √n 이하의 소인수를 반드시 가집니다. 따라서 √n 이하 소수의 배수를 지우면 모든 합성수가 지워집니다.

면접 질문

시간 복잡도가 O(n log log n)인 이유는?

소수 p마다 약 n/p칸을 지우고, 소수 역수의 합이 log log n처럼 느리게 자라기 때문입니다. n × (1/2 + 1/3 + 1/5 + ...)에 해당합니다.

면접 질문

큰 n에서 메모리를 줄이려면?

홀수만 저장해 칸 수를 절반으로 줄이거나, 비트 하나에 수 하나를 담거나, 구간을 나눠 처리하는 구간 체가 있습니다. 비트 배열과 구간 체는 접근 횟수가 같고 메모리만 줄어들며, 구간 체는 공간이 O(√n)입니다.

활용 분야

소수 표 전처리 — 여러 수의 소수 여부를 반복해서 물어야 할 때 한 번 만든 표로 판정을 O(1)에 합니다.

소인수 분해 — 지울 때 각 수를 처음 지운 소수를 기록하면 최소 소인수 표가 되어, 이후 인수분해를 소인수 개수만큼의 나눗셈으로 끝냅니다.

소수 개수와 합 — n 이하 소수의 개수나 합처럼 범위 전체에 대한 질의를 표 한 번으로 계산합니다.

함께 보면 좋은 토픽

시간 복잡도 — O(n log log n)이 어떤 위치에 있는지 봅니다.

비트 조작 트릭 — 비트 하나로 한 수를 표현해 메모리를 줄이는 방법과 이어집니다.

동적 계획법 — 앞선 결과를 표로 저장해 재사용하는 같은 발상을 봅니다.

배열 vs 연결 리스트 — 연속된 칸을 인덱스로 읽는 배열의 특성을 봅니다.

참고 자료

논문 — Gries, D., Misra, J., "A linear sieve algorithm for finding prime numbers", Communications of the ACM 21(12), 1978

교재 — Hardy, G. H., Wright, E. M., "An Introduction to the Theory of Numbers" (소수의 역수의 합에 관한 장)

교재 — Nicomachus of Gerasa, "Introduction to Arithmetic" (체에 대한 고대의 서술)

공식 문서 — Python bytearray

공식 문서 — Java BitSet

Python — 에라토스테네스의 체

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False          # 0과 1은 소수가 아니다
    ops = 0                                  # 지우기 위해 접근한 횟수
    p = 2
    while p * p <= n:                         # √n 까지만 확인
        if is_prime[p]:                       # 지워지지 않았다면 소수
            for m in range(p * p, n + 1, p):  # p² 부터 p씩 건너뛰며 지운다
                is_prime[m] = False
                ops += 1
        p += 1
    return [i for i in range(n + 1) if is_prime[i]], ops

primes, ops = sieve(50)
print(primes, len(primes), ops)
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] 15 45

배열 is_prime의 모든 칸을 처음에는 소수 후보(True)로 두고, 2부터 차례로 훑으며 아직 지워지지 않은 수 p를 소수로 확정한 뒤 p의 배수를 False로 지웁니다. 끝까지 True로 남은 수가 소수입니다. 각 수를 다른 수로 나눠 보는 시험 나눗셈과 달리 나눗셈 없이 배수를 건너뛰는 덧셈으로 지웁니다. 두 가지가 핵심입니다. 첫째, 지우기는 p × 2가 아니라 p × p부터 시작합니다. p × k에서 k가 p보다 작으면 k의 소인수가 p보다 작은 소수이므로 이미 지워졌기 때문입니다. 둘째, 바깥 반복은 p × p가 n 이하인 동안만 돕니다. 합성수는 자신의 제곱근 이하의 소인수를 가지므로 √n 이하의 소수만 처리하면 n 이하의 모든 합성수가 지워집니다. 50 이하에서는 2, 3, 5, 7만 처리하고 칸 접근은 24 + 14 + 6 + 1 = 45번이며, 소수는 15개입니다. 시각화의 체 걸러내기 탭이 보여 주는 과정과 같습니다.

Python — 슬라이스로 지우기와 n 키우기

import math

def sieve_fast(n):
    s = bytearray([1]) * (n + 1)
    s[0] = s[1] = 0
    for p in range(2, math.isqrt(n) + 1):
        if s[p]:
            s[p * p::p] = bytearray(len(range(p * p, n + 1, p)))   # 한 번에 0으로
    return [i for i in range(n + 1) if s[i]]

print(sieve_fast(50) == sieve(50)[0], len(sieve_fast(1_000_000)))   # True 78498
for n in (100, 1000, 10000, 100000, 1000000):
    print(n, sieve(n)[1])
# 100 104 / 1000 1411 / 10000 16981 / 100000 193078 / 1000000 2122048

같은 알고리즘을 슬라이스 대입으로 쓴 형태입니다. s[p * p::p]는 p²부터 끝까지 p칸씩 건너뛴 위치를 가리키고, 그 자리를 길이가 같은 0 배열로 한 번에 덮어씁니다. 파이썬 반복문을 줄여 큰 n에서 훨씬 빠르게 돌지만 지우는 횟수는 같습니다. n = 1,000,000 이하의 소수는 78,498개입니다. 아래쪽 반복문은 앞의 sieve로 n을 키워 가며 접근 횟수를 센 결과입니다. n이 10배씩 커질 때 접근 횟수는 104, 1,411, 16,981, 193,078, 2,122,048번으로, n당 횟수는 1.04, 1.41, 1.70, 1.93, 2.12로 조금씩만 늘어납니다. 이것이 O(n log log n)이 선형 시간에 가까운 이유이며, 시각화의 n이 커지면 탭이 같은 값을 보여 줍니다.

Java — boolean 배열로 체 만들기

static boolean[] sieve(int n) {
    boolean[] composite = new boolean[n + 1];      // 기본값 false = 아직 지워지지 않음
    for (int p = 2; (long) p * p <= n; p++) {
        if (!composite[p]) {
            for (int m = p * p; m <= n; m += p) composite[m] = true;
        }
    }
    return composite;
}

// 50 이하에서 composite[i]가 false인 i (i ≥ 2) → [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

자바 boolean 배열은 새로 만들면 모두 false이므로, 합성수라는 뜻의 composite 배열을 두면 초기화 반복이 필요 없습니다. 지워진 칸만 true로 바꾸고, 끝에서 false로 남은 2 이상의 수가 소수입니다. p * p가 int 범위를 넘지 않도록 long으로 올려 비교했습니다. 배열 크기가 n + 1이므로 공간은 O(n)입니다. n이 아주 크면 배열이 메모리를 많이 차지하므로, 비트 하나에 한 수를 담는 BitSet을 쓰거나 구간을 나눠 처리하는 변형을 씁니다. 다만 칸에 접근하는 횟수는 그대로입니다.

에라토스테네스의 체의 기본 원리는?

지워지지 않고 남는 수가 소수입니다.

2부터 시작해 아직 지워지지 않은 수를 소수로 확정하고, 그 수의 배수를 모두 지웁니다. 이를 반복하면 끝까지 남은 수만 소수가 됩니다.

n 이하의 소수를 구할 때 √n 까지의 소수들의 배수만 지워도 되는 이유는?

합성수 n = a × b 에서 두 인수 중 작은 쪽은 √n 이하입니다.

합성수 m은 m = a × b 로 쓸 수 있고 a, b 중 하나는 반드시 √m 이하입니다. 따라서 √n 이하 소수의 배수를 모두 지우면 n 이하의 합성수가 전부 지워집니다.

에라토스테네스의 체의 시간 복잡도는?

소수의 역수의 합이 log log n 정도로 아주 천천히 커집니다.

각 소수 p마다 약 n/p번의 배수 지우기를 하고, 이를 소수들에 대해 합하면 n × (1/2 + 1/3 + 1/5 + ...) ≈ n log log n 이 됩니다. 거의 선형에 가까운 효율입니다.