이 게시글은 CS(컴퓨터공학) 프로그래밍 기초를 어느 정도 알고 있다고 가정하고 아주 간단하게 설명하는 게시글입니다.
혹시나 모르는 부분이 있으면 댓글로 질문해주세요.
한 줄 요약 : 자연수 N 이하의 모든 소수들을 구해주는 알고리즘입니다.
소수 판정에서 해당 자연수가 소수인지 아닌지 판별하는 알고리즘을 초간단하게 설명했어요.
그런데 저는 이런 의문이 들었습니다.
"그러면 여러 개의 수들의 소수 판별은 어떻게 해야 하지?"
그래서 1부터 N까지 모든 자연수들 중에서 소수인 것만 추출하고 싶어요.
제가 알고리즘 공부하다가 이런 알고리즘을 본 적이 있습니다.
"에라토스테네스의 체" <- 이거 솔직히 말해 맨 처음에 봤을 때 뭐 이렇게 어려워 보이지? 라는 생각이 들었습니다.
하지만 지금 보니 그냥 초간단하게 생각해보면 "아하! 그냥 소수들을 다 구해주는 개쩌는 알고리즘이구나!"입니다.
오늘 그 멋진 알고리즘을 초간단하게 알아보도록 하겠습니다.
import math
def eratosthenes_sieve(n:int) -> list :
if n < 2 :
return []
is_prime:list = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False
for i in range(4, n + 1, 2) :
is_prime[i] = False
for i in range(3, int(math.sqrt(n)) + 1, 2) :
if is_prime[i] :
for j in range(i * i, n + 1, 2 * i) :
is_prime[j] = False
return [index for index, value in enumerate(is_prime) if value]
print(eratosthenes_sieve(100))자! 뭔가 어려워 보이는 소스 코드이지만 제가 하나씩 뜯어보도록 하겠습니다!
if n < 2 :
return []당연히 2 미만이면 소수들이 아무 것도 없으니 빈 리스트를 반환합니다.
is_prime:list = [True] * (n + 1)그 다음은 이것입니다.
예를 들어 n = 4인 경우 is_prime = [True, True, True, True, True]가 되며 index 범위는 0~4가 됩니다.
is_prime[0], is_prime[1] = False, False0과 1은 당연히 소수가 아니니 False(소수가 아님)으로 해줍니다.
for i in range(4, n + 1, 2) :
is_prime[i] = False2는 True(소수 맞음)이므로 4부터 해서 모든 짝수들을 False(소수가 아님)으로 해줍니다.
for i in range(3, int(math.sqrt(n)) + 1, 2) :i는 소수입니다.
int(math.sqrt(n)) + 1은 소수 판정에서 보면 알겠지만 제곱근 이하까지 탐색하면 중복 탐색을 피할 수 있습니다.
그리고 4 이상의 짝수들은 소수가 아니니 2씩 증가하도록 합니다.
즉, i = 3, 5, 7, 9, 11, 13, ...이 됩니다.
if is_prime[i] :i가 소수인지 판별하는 소스 코드입니다.
다음에 나올 코드에서 9, 15, 21, 25 등 소수가 아닌 경우 여기서 걸러줘서 중복 탐색을 피하게 됩니다.
i가 3, 5, 7, 11 등 소수이면 해당 루프를 실행하도록 합니다.
for j in range(i * i, n + 1, 2 * i) :
is_prime[j] = False여기가 바로 핵심입니다.
초기값을 i * i로 합니다.
예시로 i = 5인 경우 5 * 2, 5 * 3, 5 * 4는 그 이전 루프(i = 3)에서 이미 False 처리 되었으며 i * i는 아직 True이니 False로 바꾸기 위해 i * i로 바꾸는 것입니다.
그리고 당연히 n까지 탐색하기 위해 n + 1로 합니다.
그리고 2 * i 이게 제일 중요한데 i는 2가 아닌 소수입니다.
그러므로 j는 항상 홀수가 되어야 합니다.
그런데 여기서 만약 2 * i이 아닌 i로 하는 경우 j + i = 짝수가 되므로 중복 탐색이 발생합니다.
따라서 시간 절약을 위해 2 * i로 합니다.
[i = 3 루프]
9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69 ... 등을 모두 False로 바꿉니다.
[i = 5 루프]
15는 i = 3 루프에서 이미 탐색한 것을 확인했죠?
그러니 25, 35, 45, 55, 65, ... 등을 모두 False로 바꿉니다.
[i = 7 루프]
21, 35는 이전 루프들에서 이미 탐색한 것을 확인했죠?
49, 63, ... 등을 모두 False로 바꿉니다.
return [index for index, value in enumerate(is_prime) if value]소수 리스트를 반환해주는 코드입니다.
enumerate(list)는 해당 list의 index, value를 추출하는 함수입니다.
여기서 index는 0부터 n까지의 자연수이며 value는 True 혹은 False입니다.
만약 value = True이면 해당 index(자연수)는 소수가 맞으므로 리스트 원소에 하나 추가합니다.
print(eratosthenes_sieve(100))n = 100인 경우 해당 리스트는 다음과 같은 결과가 나옵니다.
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
신기하죠? 이렇게 해서 100 이하의 모든 소수들을 구할 수 있게 됩니다.
시간 복잡도는 O(N log N log N)입니다.
아래는 증명 과정입니다. 그냥 눈으로만 봐주세요.
이 게시글은 CS(컴퓨터공학)와 정수론을 어느 정도 알고 있다고 가정하고 설명하는 증명 과정입니다.
1. 연산 횟수(Operation Count) 모델링
에라토스테네스의 체 알고리즘에서 가장 핵심이 되는 연산은 내부 루프, 즉 "소수 $p$를 찾았을 때 그 배수들을 지우는 작업"입니다.
어떤 수 $N$까지 탐색할 때, 각 소수 $p$에 대해 발생하는 지우기 연산의 횟수는 대략 $\frac{N}{p}$ 번입니다.
- $p=2$ 일 때 연산 횟수 : $\frac{N}{2}$
- $p=3$ 일 때 연산 횟수 : $\frac{N}{3}$
- $p=5$ 일 때 연산 횟수 : $\frac{N}{5}$
- $\dots$
따라서 전체 연산 횟수 $T(N)$은 $N$ 이하의 모든 소수 $p$들에 대한 조화급수(Harmonic series over primes)의 합으로 표현할 수 있습니다.
$$ T(N) = \sum_{p \le N, \, p \in \text{Prime}} \frac{N}{p} = N \sum_{p \le N} \frac{1}{p} $$이제 우리가 증명해야 할 핵심은 뒤에 붙은 시그마 항, 즉 소수들의 역수의 합(Sum of the reciprocals of primes) $\sum_{p \le N} \frac{1}{p}$ 이 점근적으로(Asymptotically) 어떻게 동작하는지 밝혀내는 것입니다.
2. 일반 조화급수와의 비교 (직관적 접근)
먼저 소수가 아닌 모든 자연수에 대한 조화급수를 떠올려 봅시다. 미적분학에서 일반 조화급수는 자연로그에 근사한다는 것을 알고 있습니다.
$$ \sum_{n=1}^{N} \frac{1}{n} \approx \ln N $$그런데 소수들의 역수의 합은 모든 자연수의 역수의 합보다 훨씬 드문드문 존재합니다. 소수의 밀도는 소수 정리(Prime Number Theorem, PNT)에 의해 대략 $\frac{1}{\ln N}$ 에 수렴합니다.
이를 아주 거칠게 직관적으로 적분 형태로 근사해 보면, $x$ 근처에서 소수가 될 확률이 $\frac{1}{\ln x}$ 이므로 다음과 같이 쓸 수 있습니다.
$$ \sum_{p \le N} \frac{1}{p} \approx \int_{2}^{N} \frac{1}{x} \cdot \frac{1}{\ln x} \, dx $$치환적분을 사용해 봅시다. $u = \ln x$ 로 두면, $du = \frac{1}{x} dx$ 가 됩니다.
$$ \int \frac{1}{\ln x} \left(\frac{1}{x} dx\right) = \int \frac{1}{u} \, du = \ln|u| = \ln(\ln x) $$따라서, 직관적으로 소수들의 역수의 합은 이중 로그(Double Logarithm)에 비례한다는 것을 알 수 있습니다.
$$ \sum_{p \le N} \frac{1}{p} \approx \ln(\ln N) $$3. 메르텐스 제2정리 (Mertens' 2nd Theorem)에 의한 엄밀한 증명
앞서 보여드린 적분 근사는 직관적 이해를 돕기 위함이며, 해석적 정수론(Analytic Number Theory)에서는 이를 1874년 증명된 메르텐스의 제2정리(Mertens' 2nd Theorem)로 정확하게 정의하고 있습니다.
[Mertens' 2nd Theorem]
$$ \sum_{p \le N} \frac{1}{p} = \ln(\ln N) + M + O\left(\frac{1}{\ln N}\right) $$여기서 $M$은 메이셀-메르텐스 상수(Meissel-Mertens constant)로 약 $0.261497\dots$ 이며, 뒤의 $O\left(\frac{1}{\ln N}\right)$ 은 $N$이 커질수록 0에 수렴하는 오차항(Error term)입니다.
4. 최종 결론
이제 메르텐스 정리를 처음에 세웠던 전체 연산 횟수 방정식에 대입합니다.
$$ T(N) = N \sum_{p \le N} \frac{1}{p} = N \left( \ln(\ln N) + M + O\left(\frac{1}{\ln N}\right) \right) $$이를 전개하면 다음과 같습니다.
$$ T(N) = N \ln(\ln N) + M \cdot N + O\left(\frac{N}{\ln N}\right) $$알고리즘의 점근적 시간 복잡도를 표기하는 빅오 표기법(Big-O Notation)에서는 가장 빠르게 증가하는 최고차항만 남기고 상수와 하위 항을 무시합니다. 이 수식에서 가장 지배적인 항은 $N \ln(\ln N)$ 입니다.
따라서, 에라토스테네스의 체의 시간 복잡도는 최종적으로 다음과 같이 증명됩니다.
$$ \therefore O(T(N)) = O(N \log \log N) $$
결국 에라토스테네스의 체가 기적의 속도를 내는 이유는, 소수의 역수 합계가 $\log N$이 아니라 그보다 훨씬 느리게 증가하는 $\log(\log N)$으로 수축해버리는 우주의 수학적 진리(메르텐스 정리) 덕분입니다.
그런데 제가 소수 탐색 게시글에서 2씩 점프하는게 아니라 6씩 점프해서 시간을 더 단축했어요.
놀랍게도 에라토스테네스의 체에서도 6씩 점프해서 시간 절약하는 것이 가능하더라고요?
import math
def eratosthenes_sieve(n: int) -> list :
if n < 2 :
return []
is_prime:list = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False
for i in range(4, n + 1, 2) :
is_prime[i] = False
for i in range(9, n + 1, 6) :
is_prime[i] = False
LIMIT = int(math.sqrt(n)) + 1
for i in range(5, LIMIT, 6) :
if is_prime[i] :
for j in range(i * i, n + 1, 6 * i) :
is_prime[j] = False
for j in range(i * (i + 2), n + 1, 6 * i) :
is_prime[j] = False
k = i + 2
if k < LIMIT and is_prime[k] :
for j in range(k * k, n + 1, 6 * k) :
is_prime[j] = False
for j in range(k * (k + 4), n + 1, 6 * k) :
is_prime[j] = False
return [index for index, value in enumerate(is_prime) if value]
print(eratosthenes_sieve(100))이렇게 해도 소수들을 구할 수 있습니다.
예시로 i = 5인 경우 25, 35, 55, 65, 85, 95, 115, 125, ... 이렇게 돌죠?
그런 경우 1번째 j 루프에서 25, 55, 85, 115, ...를 탐색하고 2번째 j 루프에서 35, 65, 95, 125, ...를 탐색합니다.
그 다음 i = 5이니 k = 7이 되겠죠?
이런 경우 k = 7이니 49, 77, 91, 119, 133, 161, 175, ... 이렇게 돌죠?
그런 경우 1번재 j 루프에서 49, 91, 133, 175, ...를 탐색하고 2번째 j 루프에서 77, 119, 161, ...를 탐색합니다.
자 지금부터 성능 테스트를 직접 진행하겠습니다.
import math
import time
def eratosthenes_sieve(n:int) -> list :
if n < 2 :
return []
is_prime:list = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False
for i in range(4, n + 1, 2) :
is_prime[i] = False
for i in range(3, int(math.sqrt(n)) + 1, 2) :
if is_prime[i] :
for j in range(i * i, n + 1, 2 * i) :
is_prime[j] = False
return [index for index, value in enumerate(is_prime) if value]
TIME = 0.0
REPEAT = 1000
for _ in range(REPEAT) :
start_time = time.time()
eratosthenes_sieve(1000000)
end_time = time.time()
TIME += end_time - start_time
print(f"경과 시간 : {TIME / REPEAT:.6f} 초")우선 2씩 점프하는 방식입니다.
1부터 백만까지의 소수들을 구하고 1000번 정도 반복해줍니다.
결과는 어떻게 나올까요?
평균 경과 시간이 약 0.1초라는 것을 알게 됩니다.
import math
import time
def eratosthenes_sieve(n: int) -> list :
if n < 2 :
return []
is_prime:list = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False
for i in range(4, n + 1, 2) :
is_prime[i] = False
for i in range(9, n + 1, 6) :
is_prime[i] = False
LIMIT = int(math.sqrt(n)) + 1
for i in range(5, LIMIT, 6) :
if is_prime[i] :
for j in range(i * i, n + 1, 6 * i) :
is_prime[j] = False
for j in range(i * (i + 2), n + 1, 6 * i) :
is_prime[j] = False
k = i + 2
if k < LIMIT and is_prime[k] :
for j in range(k * k, n + 1, 6 * k) :
is_prime[j] = False
for j in range(k * (k + 4), n + 1, 6 * k) :
is_prime[j] = False
return [index for index, value in enumerate(is_prime) if value]
TIME = 0.0
REPEAT = 1000
for _ in range(REPEAT) :
start_time = time.time()
eratosthenes_sieve(1000000)
end_time = time.time()
TIME += end_time - start_time
print(f"경과 시간 : {TIME / REPEAT:.6f} 초")그러면 이번엔 6씩 점프하는 방식입니다.
동일한 설정을 했습니다.
결과는 어떻게 나올까요?
역시 약 0.1초가 나오므로 별 차이가 없습니다.
그러므로 실전에서 소수 탐색은 6씩 점프해야 시간 절약이 되지만 에라토스테네스의 체는 2씩 점프하는 것이 오히려 더 낫다는 결론이 나옵니다.
def eratosthenes_sieve(n:int) -> list :
if n < 2 :
return []
is_prime:list = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False
for i in range(4, n + 1, 2) :
is_prime[i] = False
for i in range(3, int(math.sqrt(n)) + 1, 2) :
if is_prime[i] :
for j in range(i * i, n + 1, 2 * i) :
is_prime[j] = False
return [index for index, value in enumerate(is_prime) if value]이게 더 효율적입니다.
'초간단 알고리즘 설명' 카테고리의 다른 글
| [알고리즘 설명][Python] 그래프 이론(graph theory) (0) | 2026.07.02 |
|---|---|
| [알고리즘 설명][C++, Python] 비트마스킹(bit mask) (0) | 2026.07.01 |
| [알고리즘 설명][Python] 큐(queue) (0) | 2026.06.25 |
| [알고리즘 설명][Python] 스택(stack) (0) | 2026.06.24 |
| [알고리즘 설명][Python] 그리디 알고리즘(greedy) (0) | 2026.06.23 |