개요[편집 / 원본 편집]
Sieve of Eratosthenes
에라토스테네스의 체(Sieve of Eratosthenes)는 고대 그리스의 수학자 에라토스테네스가 고안한 소수 판별 알고리즘이다. 기원전 240년경에 만들어진 이 알고리즘은 현대에도 여전히 효율적인 소수 탐색 방법으로 사용되고 있다.[1]
'체'라는 이름이 붙은 이유는 숫자들을 체로 거르듯이 합성수를 걸러내고 소수만 남기는 방식이기 때문이다. 마치 밀가루를 체로 거르듯이 말이다.
역사[편집 / 원본 편집]
에라토스테네스[편집 / 원본 편집]
이 알고리즘을 만든 에라토스테네스(BC 276~BC 194)는 고대 그리스의 천재 수학자이자 지리학자였다. 그는 알렉산드리아 도서관의 관장을 역임했으며, 지구의 둘레를 최초로 계산한 것으로도 유명하다.[2]
에라토스테네스는 수학, 천문학, 지리학, 시학 등 다방면에서 활약했지만, 각 분야에서 1인자는 아니었다고 한다. 그래서 당시 사람들이 그에게 '베타(β)'라는 별명을 붙였다고. 2인자의 설움 하지만 이 체 알고리즘만큼은 2000년이 넘도록 현역으로 쓰이고 있으니, 그야말로 레전드다.
알고리즘 원리[편집 / 원본 편집]
기본 아이디어[편집 / 원본 편집]
에라토스테네스의 체의 핵심 아이디어는 매우 단순하다:
소수의 배수는 모두 합성수다.
이 간단한 사실을 이용해서 2부터 시작하여 각 소수의 배수들을 지워나가면, 최종적으로 소수만 남게 된다는 것이다.
상세 알고리즘[편집 / 원본 편집]
1. 2부터 N까지의 모든 자연수를 나열한다.
- 1은 소수가 아니므로 처음부터 제외한다.[3]
2. 2를 소수로 선택하고, 2의 배수를 모두 지운다.
- 4, 6, 8, 10, 12, ... 를 전부 지운다.
- 2는 남겨둔다. 자기 자신은 지우지 않는다.
3. 남은 수 중 가장 작은 수(3)를 소수로 선택하고, 그 배수를 모두 지운다.
- 6, 9, 12, 15, 18, ... 을 전부 지운다.
- 이때 6, 12 등은 이미 지워진 상태다. 중복 작업이지만 상관없다.
4. 이 과정을 반복한다.
- 다음은 5의 배수(10, 15, 20, 25, ...)를 지운다.
- 그 다음은 7의 배수를 지운다.
- [math]\displaystyle{ \sqrt{N} }[/math]까지만 반복하면 된다.[4]
5. 남은 수들이 모두 소수다.
구체적 예시[편집 / 원본 편집]
30까지의 소수 구하기[편집 / 원본 편집]
2부터 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
[1단계: 2의 배수 제거] 2는 소수로 확정. 4, 6, 8, 10, 12, ... 를 제거
2 3 X 5 X 7 X 9 X 11 X 13 X 15 X 17 X 19 X 21 X 23 X 25 X 27 X 29 X
[2단계: 3의 배수 제거] 3은 소수로 확정. 6, 9, 12, 15, 18, ... 을 제거
2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X 25 X X X 29 X
[3단계: 5의 배수 제거] 5는 소수로 확정. 10, 15, 20, 25, 30을 제거
2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X X 29 X
[종료: [math]\displaystyle{ \sqrt{30}\approx 5.48 }[/math] 이므로 5까지만 확인하면 됨] 7은 [math]\displaystyle{ 7^2=49 }[/math] 이고 [math]\displaystyle{ 49\gt 30 }[/math]이므로 확인할 필요 없음.
최종 결과: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 (총 10개)
시간 복잡도[편집 / 원본 편집]
성능 분석[편집 / 원본 편집]
에라토스테네스의 체의 시간 복잡도는 [math]\displaystyle{ O(N\log\log N) }[/math]이다.[5]
이게 얼마나 빠른가 하면:
- 단순 소수 판별법: 각 수마다 [math]\displaystyle{ \sqrt{N} }[/math]까지 나눠보기 → [math]\displaystyle{ O(N^{1.5}) }[/math]
- 에라토스테네스의 체: 배수 지우기 → [math]\displaystyle{ O(N\log\log N) }[/math]
예를 들어 [math]\displaystyle{ N=1{,}000{,}000 }[/math]일 때:
- 단순 방법: 약 [math]\displaystyle{ 1{,}000{,}000^{1.5}\approx 10^{12} }[/math] 번의 연산
- 에라토스테네스: 약 [math]\displaystyle{ N\log\log N }[/math] 수준의 연산(상수 및 구현에 따라 달라짐)
최적화 기법[편집 / 원본 편집]
짝수 건너뛰기[편집 / 원본 편집]
2를 제외한 모든 짝수는 합성수이므로, 홀수만 확인하면 된다.
- 메모리 사용량 감소
- 연산 횟수도 감소
[math]\displaystyle{ \sqrt{N} }[/math]까지만 체크[편집 / 원본 편집]
[math]\displaystyle{ N }[/math] 이하의 합성수는 반드시 [math]\displaystyle{ \sqrt{N} }[/math] 이하의 소인수를 가진다. 따라서 [math]\displaystyle{ \sqrt{N} }[/math]까지만 확인하면 충분하다.
증명: 합성수 [math]\displaystyle{ M=a\times b }[/math]라고 하자. ([math]\displaystyle{ a\le b }[/math]) 만약 [math]\displaystyle{ a\gt \sqrt{M} }[/math]이라면, [math]\displaystyle{ b\gt \sqrt{M} }[/math]도 성립한다. 그러면 [math]\displaystyle{ a\times b\gt \sqrt{M}\times\sqrt{M}=M }[/math]이 되어 모순. 따라서 [math]\displaystyle{ a\le\sqrt{M} }[/math]이거나 [math]\displaystyle{ b\le\sqrt{M} }[/math]이다.
[math]\displaystyle{ i^2 }[/math]부터 시작하기[편집 / 원본 편집]
소수 [math]\displaystyle{ p }[/math]의 배수를 지울 때, [math]\displaystyle{ 2p,3p,4p,\dots }[/math]부터 지우지 말고 [math]\displaystyle{ p^2 }[/math]부터 지우면 된다.
- 왜냐하면 [math]\displaystyle{ 2p,3p,\dots,(p-1)p }[/math]는 이미 이전 단계에서 지워졌기 때문이다.
- 예: 7의 배수를 지울 때 [math]\displaystyle{ 14(=2\times 7),21(=3\times 7) }[/math] 등은 이미 2나 3의 배수로 지워진다.
공간 복잡도[편집 / 원본 편집]
에라토스테네스의 체는 [math]\displaystyle{ O(N) }[/math]의 공간이 필요하다. [math]\displaystyle{ 0 }[/math]부터 [math]\displaystyle{ N }[/math]까지 각 정수에 대해 "소수인가?"를 저장해야 하기 때문이다.
비트 최적화[편집 / 원본 편집]
Boolean 배열 대신 비트 배열을 사용하면 메모리를 [math]\displaystyle{ \frac{1}{8} }[/math]로 줄일 수 있다.[6]
예: 1억까지의 소수를 구할 때(개념적 예시)
- Boolean 배열: 약 100MB 수준
- 비트 배열: 약 12.5MB 수준
- 홀수만 저장: 약 6.25MB 수준
구현 예시[편집 / 원본 편집]
Python[편집 / 원본 편집]
"""
에라토스테네스의 체 (Python 3.x)
- 입력: 표준 입력으로 정수 N (N >= 0)
- 출력: 2 이상 N 이하의 모든 소수를 공백으로 구분하여 한 줄에 출력
(소수가 없으면 빈 줄)
이 코드는 "생략 없이" 실행 가능한 완전한 예시를 제공한다.
"""
from __future__ import annotations
def sieve_of_eratosthenes(n: int) -> list[int]:
"""
에라토스테네스의 체로 n 이하의 모든 소수를 구한다.
Args:
n (int): 상한 값
Returns:
list[int]: 2 이상 n 이하의 소수 목록
"""
# n이 2보다 작으면 소수가 없다.
if n < 2:
return []
# is_prime[i] == True -> i는 소수 후보
# is_prime[i] == False -> i는 합성수(또는 0/1)
is_prime = [True] * (n + 1)
# 0과 1은 소수가 아니므로 False로 표시한다.
is_prime[0] = False
is_prime[1] = False
# 2부터 √n까지 확인한다.
# i가 소수라면 i의 배수들을 합성수로 지운다.
limit = int(n ** 0.5)
for i in range(2, limit + 1):
if is_prime[i]:
# i*i 미만의 배수(2i, 3i, ..., (i-1)i)는
# 더 작은 소수 단계에서 이미 지워졌으므로 i*i부터 시작한다.
start = i * i
step = i
for j in range(start, n + 1, step):
is_prime[j] = False
# True로 남아 있는 인덱스만 소수이므로 리스트로 추출한다.
primes: list[int] = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
return primes
def main() -> None:
"""
프로그램 진입점.
표준 입력에서 N을 읽고,
n 이하의 소수를 공백으로 구분해 출력한다.
"""
import sys
data = sys.stdin.read().strip()
if not data:
# 입력이 비어 있으면 아무 것도 출력하지 않는다.
return
n = int(data)
primes = sieve_of_eratosthenes(n)
# 소수 목록을 한 줄로 출력한다.
# 소수가 없으면 빈 줄이 출력된다.
sys.stdout.write(" ".join(map(str, primes)) + "\n")
if __name__ == "__main__":
main()C++[편집 / 원본 편집]
/*
에라토스테네스의 체 (C++)
- 입력: 표준 입력으로 정수 N (N >= 0)
- 출력: 2 이상 N 이하의 모든 소수를 공백으로 구분하여 한 줄에 출력
(소수가 없으면 빈 줄)
이 코드는 "생략 없이" 컴파일/실행 가능한 완전한 예시를 제공한다.
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
static std::vector<int> sieve_of_eratosthenes(int n) {
// n이 2보다 작으면 소수가 없다.
if (n < 2) {
return {};
}
// is_prime[i] == true -> i는 소수 후보
// is_prime[i] == false -> i는 합성수(또는 0/1)
std::vector<bool> is_prime(static_cast<std::size_t>(n + 1), true);
// 0과 1은 소수가 아니다.
is_prime[0] = false;
is_prime[1] = false;
// 2부터 √n까지 확인한다.
int limit = static_cast<int>(std::sqrt(static_cast<double>(n)));
for (int i = 2; i <= limit; i++) {
if (is_prime[i]) {
// i*i 미만의 배수는 이미 더 작은 소수 단계에서 지워졌으므로 i*i부터 시작한다.
long long start = 1LL * i * i;
for (long long j = start; j <= n; j += i) {
is_prime[static_cast<std::size_t>(j)] = false;
}
}
}
// 소수만 추출한다.
std::vector<int> primes;
primes.reserve(n / 10); // 대략적인 예약(정확하지 않아도 무방)
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
primes.push_back(i);
}
}
return primes;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
if (!(std::cin >> n)) {
// 입력이 없으면 종료한다.
return 0;
}
std::vector<int> primes = sieve_of_eratosthenes(n);
// 공백으로 구분해 한 줄 출력한다.
for (std::size_t i = 0; i < primes.size(); i++) {
if (i > 0) {
std::cout << ' ';
}
std::cout << primes[i];
}
std::cout << '\n';
return 0;
}JavaScript[편집 / 원본 편집]
/*
에라토스테네스의 체 (JavaScript / Node.js)
- 입력: 표준 입력으로 정수 N (N >= 0)
- 출력: 2 이상 N 이하의 모든 소수를 공백으로 구분하여 한 줄에 출력
(소수가 없으면 빈 줄)
이 코드는 "생략 없이" 실행 가능한 완전한 예시를 제공한다.
*/
"use strict";
/**
* 에라토스테네스의 체로 n 이하의 모든 소수를 구한다.
*
* @param {number} n - 상한 값
* @returns {number[]} - 2 이상 n 이하의 소수 목록
*/
function sieveOfEratosthenes(n) {
// n이 2보다 작으면 소수가 없다.
if (n < 2) {
return [];
}
// isPrime[i] === true -> i는 소수 후보
// isPrime[i] === false -> i는 합성수(또는 0/1)
const isPrime = new Array(n + 1).fill(true);
// 0과 1은 소수가 아니다.
isPrime[0] = false;
isPrime[1] = false;
// 2부터 √n까지 확인한다.
const limit = Math.floor(Math.sqrt(n));
for (let i = 2; i <= limit; i++) {
if (isPrime[i]) {
// i*i 미만의 배수는 이미 더 작은 소수 단계에서 지워졌으므로 i*i부터 시작한다.
for (let j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
// 소수만 추출한다.
const primes = [];
for (let i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.push(i);
}
}
return primes;
}
/**
* 프로그램 진입점.
* 표준 입력에서 N을 읽고, 소수 목록을 공백으로 구분해 출력한다.
*/
function main() {
const fs = require("fs");
const input = fs.readFileSync(0, "utf8").trim();
if (input.length === 0) {
// 입력이 비어 있으면 아무 것도 출력하지 않는다.
return;
}
const n = Number(input);
const primes = sieveOfEratosthenes(n);
process.stdout.write(primes.join(" ") + "\n");
}
main();응용[편집 / 원본 편집]
소인수분해[편집 / 원본 편집]
에라토스테네스의 체를 변형하면 모든 수의 소인수분해를 빠르게 할 수 있다.
각 수에 대해 "가장 작은 소인수"를 저장해두면, [math]\displaystyle{ O(\log N) }[/math] 시간에 소인수분해가 가능하다.
"""
Smallest Prime Factor(SPF)를 저장하는 체 + 빠른 소인수분해 (Python 3.x)
- sieve_with_spf(n): 2..n 범위에 대해 각 수의 최소 소인수(spf)를 계산한다.
- factorize(x, spf): spf를 이용해 x를 소인수분해하여 소인수 목록(중복 포함)을 반환한다.
이 코드는 "생략 없이" 실행 가능한 완전한 예시를 제공한다.
"""
from __future__ import annotations
def sieve_with_spf(n: int) -> list[int]:
"""
0..n 범위에서 각 정수의 최소 소인수(SPF: Smallest Prime Factor)를 저장한다.
spf[x]는 x의 최소 소인수이며,
소수 p에 대해서는 spf[p] == p가 된다.
Args:
n (int): 상한 값
Returns:
list[int]: spf 배열 (길이 n+1)
"""
# spf[i]를 i로 초기화한다.
# 이후 합성수에 대해서만 더 작은 소인수로 갱신한다.
spf = list(range(n + 1))
if n >= 0:
spf[0] = 0
if n >= 1:
spf[1] = 1
limit = int(n ** 0.5)
for i in range(2, limit + 1):
# spf[i] == i 이면 i는 소수이다.
if spf[i] == i:
# i*i부터 시작하는 이유:
# i의 더 작은 배수들은 이미 더 작은 소수 단계에서 처리되었기 때문이다.
start = i * i
for j in range(start, n + 1, i):
# 아직 최소 소인수가 갱신되지 않은 경우에만 i로 설정한다.
if spf[j] == j:
spf[j] = i
return spf
def factorize(x: int, spf: list[int]) -> list[int]:
"""
spf를 사용하여 x를 소인수분해한다.
각 단계에서 x를 spf[x]로 나누므로 시간은 대략 O(log x) 수준이다.
Args:
x (int): 소인수분해할 정수 (x >= 1)
spf (list[int]): sieve_with_spf로 만든 최소 소인수 배열
Returns:
list[int]: 소인수 목록(중복 포함)
"""
factors: list[int] = []
while x > 1:
p = spf[x]
factors.append(p)
x //= p
return factors
def main() -> None:
"""
예시 실행:
- 100까지 spf를 만든 뒤 60을 소인수분해한다.
"""
spf = sieve_with_spf(100)
print(factorize(60, spf)) # [2, 2, 3, 5]
if __name__ == "__main__":
main()오일러 파이 함수[편집 / 원본 편집]
오일러 파이 함수 [math]\displaystyle{ \varphi(n) }[/math] (n 이하의 n과 서로소인 수의 개수)도 체를 이용해 빠르게 계산할 수 있다.
뫼비우스 함수[편집 / 원본 편집]
뫼비우스 함수 [math]\displaystyle{ \mu(n) }[/math]도 마찬가지로 체로 전처리가 가능하다.
변형 알고리즘[편집 / 원본 편집]
선형 체 (Linear Sieve)[편집 / 원본 편집]
에라토스테네스의 체의 단점은 같은 수를 여러 번 지운다는 것이다.
- 예: 12는 2의 배수로 한 번, 3의 배수로 또 한 번 지워진다.
선형 체는 각 수를 정확히 한 번만 지워서 [math]\displaystyle{ O(N) }[/math]의 시간 복잡도를 달성한다.[7]
분할 체 (Segmented Sieve)[편집 / 원본 편집]
매우 큰 범위의 소수를 구할 때는 메모리 문제가 발생한다. 이때 구간을 나눠서 처리하는 방법이 분할 체다.
예: 10억~10억 1000만 사이의 소수를 구하려면? 1. [math]\displaystyle{ \sqrt{10^9}\approx 31623 }[/math]까지의 소수를 먼저 구한다. 2. 이 소수들로 10억~10억 1000만 구간을 체로 거른다. 3. 메모리는 1000만개만 필요하다. (10억개가 필요하지 않다)
장단점[편집 / 원본 편집]
장점[편집 / 원본 편집]
- 매우 빠르다: [math]\displaystyle{ O(N\log\log N) }[/math]은 거의 선형 시간
- 구현이 간단하다: 초보자도 쉽게 이해 가능
- 직관적이다: "배수를 지운다"는 개념이 명확함
- 다목적: 소수 판별, 소인수분해, 오일러 함수 등 다양하게 응용 가능
단점[편집 / 원본 편집]
- 메모리를 많이 쓴다: [math]\displaystyle{ O(N) }[/math] 공간 필요
* [math]\displaystyle{ N=10^9 }[/math] 같은 큰 값에서는 메모리 부담이 커질 수 있다.
- 한 번에 한 범위만: 예를 들어 10억~20억번째 소수를 직접 구하려면 더 작은 범위를 포함해 넓게 처리해야 할 수 있다.
* 분할 체로 완화 가능
- 매우 큰 소수: [math]\displaystyle{ N }[/math]이 너무 크면 메모리 부족
* 밀러-라빈 소수판별법 같은 확률적 방법 사용
실생활 활용[편집 / 원본 편집]
암호학[편집 / 원본 편집]
RSA 암호에서 큰 소수를 찾을 때 사용된다. 물론 수백 자리 소수는 에라토스테네스로 직접 찾기 어렵고 확률적 방법을 쓰지만, 작은 소수를 미리 걸러낼 때 활용된다.
프로그래밍 대회[편집 / 원본 편집]
알고리즘 문제 해결 전략에서 빈출되는 기법이다. 백준 온라인 저지, 코드포스, 프로젝트 오일러 등에서 자주 출제된다.
특히 프로젝트 오일러의 많은 문제들이 에라토스테네스의 체를 요구한다.
수학 연구[편집 / 원본 편집]
- 골드바흐 추측 검증
- 쌍둥이 소수 탐색
- 소수 분포 연구
- 리만 가설 실험
흥미로운 사실[편집 / 원본 편집]
- 2000년 이상 현역: 기원전 240년에 만들어진 알고리즘이 현대에도 쓰인다.[8]
- 최초의 체계적 알고리즘?: 수학사에서 가장 오래된 알고리즘 중 하나로 언급된다.
- 이름의 유래: 실제로 고대 그리스에서는 구멍 뚫린 파피루스에 숫자를 써서 합성수에 해당하는 구멍을 막는 방식으로 사용했다는 이야기가 전해진다.[9]
- [math]\displaystyle{ 10^{23} }[/math]까지 계산됨: 현대 컴퓨팅으로 매우 큰 범위의 소수 관련 계산이 수행된 바가 있으나, 사용된 알고리즘은 문제에 따라 다양하다.
- 메르센 소수는 예외: [math]\displaystyle{ 2^{82{,}589{,}933}-1 }[/math] 같은 메르센 소수는 범위 체로 직접 탐색하기 어렵다. 이런 경우에는 뤼카-레머 판별법 같은 특수한 판별법을 쓴다.
교육적 가치[편집 / 원본 편집]
에라토스테네스의 체는 알고리즘 교육에 매우 좋은 예시다:
1. 최적화 사고: 단순한 방법 → 개선된 방법으로의 진화 2. 시간-공간 트레이드오프: 메모리를 써서 시간을 아낀다 3. 수학과 프로그래밍의 융합: 수학적 성질을 코드로 구현 4. 점진적 개선: 짝수 건너뛰기, [math]\displaystyle{ i^2 }[/math]부터 시작 등 단계적 최적화
많은 알고리즘 교과서에서 초반에 에라토스테네스의 체를 다루는 이유로 자주 언급된다.
비교: 다른 소수 판별 방법들[편집 / 원본 편집]
| 방법 | 시간 복잡도 | 공간 복잡도 | 특징 |
|---|---|---|---|
| 시행 나눗셈 | [math]\displaystyle{ O(\sqrt{N}) }[/math] | [math]\displaystyle{ O(1) }[/math] | 단일 수 판별에 적합 |
| 에라토스테네스의 체 | [math]\displaystyle{ O(N\log\log N) }[/math] | [math]\displaystyle{ O(N) }[/math] | 범위 내 모든 소수 |
| 선형 체 | [math]\displaystyle{ O(N) }[/math] | [math]\displaystyle{ O(N) }[/math] | 이론상 최적, 구현 복잡 |
| 밀러-라빈 | [math]\displaystyle{ O(k\log^3 N) }[/math] | [math]\displaystyle{ O(1) }[/math] | 확률적, 매우 큰 수 |
| AKS 소수판별법 | [math]\displaystyle{ O(\log^6 N) }[/math] | [math]\displaystyle{ O(\log N) }[/math] | 결정적, 이론적 의의 |
관련 문제[편집 / 원본 편집]
백준 온라인 저지[편집 / 원본 편집]
- 1929번: 소수 구하기 - 기본 문제
- 1016번: 제곱 ㄴㄴ 수 - 응용 문제
- 6588번: 골드바흐의 추측 - 에라토스테네스 + 골드바흐
프로젝트 오일러[편집 / 원본 편집]
- Problem 10: 200만 이하 모든 소수의 합
- Problem 50: 가장 긴 소수 연속합
여담[편집 / 원본 편집]
- 에라토스테네스는 이 알고리즘 외에도 지구 둘레 측정, 윤년 계산, 지리학 좌표계 등을 개발한 것으로 알려져 있다.
- 체를 뜻하는 영어 "Sieve"는 밀가루를 거르는 체를 말한다. 실제로 밀가루 체와 작동 원리가 비슷하다.
- 이 알고리즘은 병렬화가 비교적 쉽다. 각 구간을 독립적으로 처리할 수 있어서 멀티코어 환경에서 효율적으로 구현될 수 있다.
- 디리클레 정리를 이용하면 특정 등차수열 내의 소수만 골라내는 이론적 논의로도 확장할 수 있다.
관련 문서[편집 / 원본 편집]
외부 링크[편집 / 원본 편집]
각주[편집 / 원본 편집]
- ↑ 특히 특정 범위 내의 모든 소수를 구할 때 매우 효율적이다.
- ↑ 그의 계산값은 실제 지구 둘레와 오차가 2% 미만이었다고 전해진다.
- ↑ 1은 역사적으로 소수로 분류되기도 했지만, 현대 수학에서는 소수의 정의에서 제외한다.
- ↑ N보다 작은 합성수는 반드시 [math]\displaystyle{ \sqrt{N} }[/math] 이하의 소인수를 가진다.
- ↑ 정확히는 [math]\displaystyle{ O(N\log\log N) }[/math]이지만, 실용적으로는 거의 [math]\displaystyle{ O(N) }[/math]에 가깝다고 알려져 있다.
- ↑ 1바이트는 8비트이므로, 비트 단위로 저장하면 같은 정보를 더 적은 메모리로 표현할 수 있다.
- ↑ 이론적으로는 더 빠르지만, 실제 구현에서는 에라토스테네스의 체가 캐시 효율성 때문에 더 빠를 수 있다.
- ↑ 알고리즘 자체는 고전이지만, 구현과 최적화는 현대 하드웨어에 맞추어 계속 발전해 왔다.
- ↑ 정확한 사료가 충분히 남아 있지 않아 전승 수준의 설명으로 다루어지는 경우가 있다.