에라토스테네스의 체 - Baleine d'Étain

1681 words

8 minutes

에라토스테네스의 체

2026-07-29

Algorithm

/

Number theory

/

Python

소수 판정#

알고리즘 문제를 풀다보면 소수를 판정해야 하는 때가 있다.

그냥 어떤 수를 주고 소수인지 아닌지 판정하라는건 쉽다.
1과 자기 자신으로만 나누어떨어져야 하기 때문에 다음과 같이 판별할 수 있다.

1
def is_prime(N: int):
2
    if N < 2:
3
        return False
4

5
    for divisor in range(2, N):  # 자기 자신 전까지
6
        if N % divisor == 0:
7
            return False
8

9
    return True

위 코드는 divisor를 2부터 N-1까지 탐색하므로 시간 복잡도는 $O(N)$ 이다.
그런데 사실 divisor는 N-1이 아니라 isqrt(N)까지만 보면 된다.
탐색 범위를 range(2, isqrt(N) + 1)로 줄일 경우 시간 복잡도는 $O(\sqrt{N})$ 이다.

특정 범위의 모든 소수 구하기#

그런데 이제 누군가는 생각한거다. 그냥 1이랑 N 사이에 있는 모든 소수를 구해놓으면 안되냐고.
에라토스테네스의 체는 길이 N+1짜리 배열에서 인덱스의 값이 True인지 False인지로 해당 인덱스가 소수인지 아닌지 판별할 수 있게 한다.

구현#

1
from math import isqrt
2

3

4
def sieve(N: int) -> list[int]:
5
    if N < 2:
6
        return []
7

8
    is_prime = [True] * (N + 1)
9
    is_prime[0] = False
10
    is_prime[1] = False
11

12
    for i in range(2, isqrt(N) + 1):
13
        if not is_prime[i]:
14
            continue
15

16
        for multiple in range(i * i, N + 1, i):
17
            is_prime[multiple] = False
18

19
    return [
20
        number
21
        for number in range(2, N + 1)
22
        if is_prime[number]
23
    ]

논리는 생각보다 간단하다. 먼저 True로 초기화된 길이 N+1짜리 배열을 준비한다.
그리고 소수가 아닌 수들을 찾으며 해당 인덱스의 배열값을 False로 바꿔주는거다.

0과 1은 소수가 아니니까 직접 False로 바꿔주면 되고, 이중반복문이 이 알고리즘의 핵심이다.
2부터 시작해서 2X2, 2X3, … 모든 2의 배수들의 인덱스에 대해 배열값을 False로 바꾼다.

누군가의 배수 = 1이랑 자기 자신 이외 약수가 있다 = 소수가 아니다 라는 것
반대로 합성수라면 1이랑 자기 자신 이외의 약수가 있고, 그 약수의 배수를 지우는 과정에서 체크될 수 밖에 없다.

이중 반복문#

첫번째 반복문의 i : 이 수의 배수를 확인하고 싶습니다
두번째 반복문의 multiple : i의 배수들을 소수가 아니라고 체크하겠습니다

여기서 가질 수 있는 의문 2가지는

왜 첫번째 반복문은 isqrt(N)까지만 보냐
왜 두번째 반복문은 i * i 부터 보냐

일텐데 단순하게 그 범위만 보면 되기 때문이다.

`isqrt(N)`까지만 보는 이유#

isqrt는 integer square root, 즉 제곱근한 값에서 내림을 해서 정수로 표현한 수이다.
소수를 판정하는데 왜 제곱근이 나오는걸까?

N 이하의 어떤 합성수 m이 a와 b의 곱으로 표현된다고 해보자. 그러면 a와 b 중에 하나는 무조건 m의 제곱근보다 작거나 같다.
왜 그런지는 귀류법으로 증명할 수 있는데, 둘 다 m의 제곱근보다 크다고 해보자. 그러면 둘의 곱은 m보다 큰 수여야 하는 모순이 발생한다.

그러니까 N 이하의 합성수를 지우기 위해서는 N의 제곱근까지만 확인해보면 된다는 뜻이다.
1이 아닌 어떤 두 수의 곱으로 표현된다면 둘 중에 하나는 무조건 그 수의 제곱근보다 작거나 같으니까.

`i * i`부터 보는 이유#

이건 그냥 중복을 피하기 위해서다.
3 * 2를 생각해보자. 이건 i=2일 때 이미 2 * 3으로 확인한 숫자다.
multiple이 i * j이고 j < i라면 그건 앞에서 더 작은 소수의 배수로 이미 처리된 값이라서 볼 필요가 없다.

그래서 i * i부터 탐색을 시작하면 되는거다. 배수만 확인하니까 스텝은 당연히 i인거고.

복잡도#

이중 반복문이라서 얼핏 보면 $O(N^2)$ 처럼 보이지만 실제로는 그렇지 않다.

i=2일 때는 N개를 전부 보는게 아니라 2의 배수만 보니까 대략 $\frac{N}{2}$ 번,
i=3일 때는 3의 배수만 보니까 대략 $\frac{N}{3}$ 번 반복한다.
4처럼 이미 소수가 아니라고 체크된 수는 건너뛰고, 5에서는 다시 대략 $\frac{N}{5}$ 번 반복한다.

즉 반복 횟수의 상한을 단순하게 잡으면 대충 이런 모양이다.

\frac{N}{2} + \frac{N}{3} + \frac{N}{5} + \frac{N}{7} + \cdots

N을 밖으로 빼면 다음과 같다.

N \left(\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \cdots\right)

괄호 안은 소수들의 역수를 더한 값인데, 이 값은 N이 커질 때 대략 $\log \log N$ 만큼 아주 느리게 증가한다.
그래서 에라토스테네스의 체의 시간 복잡도는 $O(N \log \log N)$ 이다.

정확한 수학적 증명까지 외울 필요는 없고, 각 소수마다 N번 도는게 아니라 그 소수의 배수만큼만 돈다고 이해하면 된다.
마지막에 is_prime 배열을 한 번 훑어 소수 목록을 만드는 작업은 $O(N)$ 인데, 전체 시간 복잡도는 그대로 $O(N \log \log N)$ 이다.