Gaon12: 시작

2026-01-17T11:40:57Z

시작

새 문서

== 개요 ==
''Sieve of Eratosthenes''

'''에라토스테네스의 체'''(Sieve of Eratosthenes)는 고대 그리스의 수학자 [[에라토스테네스]]가 고안한 [[소수]] 판별 [[알고리즘]]이다. 기원전 240년경에 만들어진 이 알고리즘은 현대에도 여전히 효율적인 소수 탐색 방법으로 사용되고 있다.<ref>특히 특정 범위 내의 모든 소수를 구할 때 매우 효율적이다.</ref>

'체'라는 이름이 붙은 이유는 숫자들을 체로 거르듯이 합성수를 걸러내고 소수만 남기는 방식이기 때문이다. 마치 밀가루를 체로 거르듯이 말이다.

== 역사 ==
=== 에라토스테네스 ===
이 알고리즘을 만든 [[에라토스테네스]](BC 276~BC 194)는 고대 그리스의 천재 수학자이자 지리학자였다. 그는 [[알렉산드리아 도서관]]의 관장을 역임했으며, 지구의 둘레를 최초로 계산한 것으로도 유명하다.<ref>그의 계산값은 실제 지구 둘레와 오차가 2% 미만이었다고 전해진다.</ref>

에라토스테네스는 수학, 천문학, 지리학, 시학 등 다방면에서 활약했지만, 각 분야에서 1인자는 아니었다고 한다. 그래서 당시 사람들이 그에게 '베타(β)'라는 별명을 붙였다고. ~~2인자의 설움~~ 하지만 이 체 알고리즘만큼은 2000년이 넘도록 현역으로 쓰이고 있으니, 그야말로 '''레전드'''다.

== 알고리즘 원리 ==
=== 기본 아이디어 ===
에라토스테네스의 체의 핵심 아이디어는 매우 단순하다:

'''소수의 배수는 모두 합성수다.'''

이 간단한 사실을 이용해서 2부터 시작하여 각 소수의 배수들을 지워나가면, 최종적으로 소수만 남게 된다는 것이다.

=== 상세 알고리즘 ===
1. '''2부터 N까지의 모든 자연수를 나열한다.'''
:* 1은 소수가 아니므로 처음부터 제외한다.<ref>1은 역사적으로 소수로 분류되기도 했지만, 현대 수학에서는 소수의 정의에서 제외한다.</ref>

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>\sqrt{N}</math>까지만 반복하면 된다.<ref>N보다 작은 합성수는 반드시 <math>\sqrt{N}</math> 이하의 소인수를 가진다.</ref>

5. '''남은 수들이 모두 소수다.'''

== 구체적 예시 ==
=== 30까지의 소수 구하기 ===
2부터 30까지의 소수를 찾는 과정을 '''단계별'''로 살펴보자.

'''[초기 상태]'''
<pre>
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
</pre>

'''[1단계: 2의 배수 제거]'''
2는 소수로 확정. 4, 6, 8, 10, 12, ... 를 제거
<pre>
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
</pre>

'''[2단계: 3의 배수 제거]'''
3은 소수로 확정. 6, 9, 12, 15, 18, ... 을 제거
<pre>
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
</pre>

'''[3단계: 5의 배수 제거]'''
5는 소수로 확정. 10, 15, 20, 25, 30을 제거
<pre>
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
</pre>

'''[종료: <math>\sqrt{30}\approx 5.48</math> 이므로 5까지만 확인하면 됨]'''
7은 <math>7^2=49</math> 이고 <math>49>30</math>이므로 확인할 필요 없음.

'''최종 결과: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29''' (총 10개)

== 시간 복잡도 ==
=== 성능 분석 ===
에라토스테네스의 체의 [[시간 복잡도]]는 '''<math>O(N\log\log N)</math>'''이다.<ref>정확히는 <math>O(N\log\log N)</math>이지만, 실용적으로는 거의 <math>O(N)</math>에 가깝다고 알려져 있다.</ref>

이게 얼마나 빠른가 하면:
* '''단순 소수 판별법''': 각 수마다 <math>\sqrt{N}</math>까지 나눠보기 → <math>O(N^{1.5})</math>
* '''에라토스테네스의 체''': 배수 지우기 → <math>O(N\log\log N)</math>

예를 들어 <math>N=1{,}000{,}000</math>일 때:
* 단순 방법: 약 <math>1{,}000{,}000^{1.5}\approx 10^{12}</math> 번의 연산
* 에라토스테네스: 약 <math>N\log\log N</math> 수준의 연산(상수 및 구현에 따라 달라짐)

=== 최적화 기법 ===
==== 짝수 건너뛰기 ====
2를 제외한 모든 짝수는 합성수이므로, 홀수만 확인하면 된다.
* 메모리 사용량 감소
* 연산 횟수도 감소

==== <math>\sqrt{N}</math>까지만 체크 ====
<math>N</math> 이하의 합성수는 반드시 <math>\sqrt{N}</math> 이하의 소인수를 가진다. 따라서 <math>\sqrt{N}</math>까지만 확인하면 충분하다.

'''증명:'''
합성수 <math>M=a\times b</math>라고 하자. (<math>a\le b</math>)
만약 <math>a>\sqrt{M}</math>이라면, <math>b>\sqrt{M}</math>도 성립한다.
그러면 <math>a\times b>\sqrt{M}\times\sqrt{M}=M</math>이 되어 모순.
따라서 <math>a\le\sqrt{M}</math>이거나 <math>b\le\sqrt{M}</math>이다.

==== <math>i^2</math>부터 시작하기 ====
소수 <math>p</math>의 배수를 지울 때, <math>2p,3p,4p,\dots</math>부터 지우지 말고 '''<math>p^2</math>'''부터 지우면 된다.
* 왜냐하면 <math>2p,3p,\dots,(p-1)p</math>는 이미 이전 단계에서 지워졌기 때문이다.
* 예: 7의 배수를 지울 때 <math>14(=2\times 7),21(=3\times 7)</math> 등은 이미 2나 3의 배수로 지워진다.

== 공간 복잡도 ==
에라토스테네스의 체는 '''<math>O(N)</math>'''의 공간이 필요하다. <math>0</math>부터 <math>N</math>까지 각 정수에 대해 "소수인가?"를 저장해야 하기 때문이다.

=== 비트 최적화 ===
Boolean 배열 대신 비트 배열을 사용하면 메모리를 <math>\frac{1}{8}</math>로 줄일 수 있다.<ref>1바이트는 8비트이므로, 비트 단위로 저장하면 같은 정보를 더 적은 메모리로 표현할 수 있다.</ref>

예: 1억까지의 소수를 구할 때(개념적 예시)
* Boolean 배열: 약 100MB 수준
* 비트 배열: 약 12.5MB 수준
* 홀수만 저장: 약 6.25MB 수준

== 구현 예시 ==
=== Python ===
<syntaxhighlight lang="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()
</syntaxhighlight>

=== C++ ===
<syntaxhighlight lang="cpp">
/*
에라토스테네스의 체 (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;
}
</syntaxhighlight>

=== JavaScript ===
<syntaxhighlight lang="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();
</syntaxhighlight>

== 응용 ==
=== 소인수분해 ===
에라토스테네스의 체를 변형하면 '''모든 수의 소인수분해'''를 빠르게 할 수 있다.

각 수에 대해 "가장 작은 소인수"를 저장해두면, <math>O(\log N)</math> 시간에 소인수분해가 가능하다.

<syntaxhighlight lang="python">
"""
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()
</syntaxhighlight>

=== 오일러 파이 함수 ===
[[오일러 파이 함수]] <math>\varphi(n)</math> (n 이하의 n과 서로소인 수의 개수)도 체를 이용해 빠르게 계산할 수 있다.

=== 뫼비우스 함수 ===
[[뫼비우스 함수]] <math>\mu(n)</math>도 마찬가지로 체로 전처리가 가능하다.

== 변형 알고리즘 ==
=== 선형 체 (Linear Sieve) ===
에라토스테네스의 체의 단점은 '''같은 수를 여러 번 지운다'''는 것이다.
* 예: 12는 2의 배수로 한 번, 3의 배수로 또 한 번 지워진다.

'''선형 체'''는 각 수를 '''정확히 한 번만''' 지워서 '''<math>O(N)</math>'''의 시간 복잡도를 달성한다.<ref>이론적으로는 더 빠르지만, 실제 구현에서는 에라토스테네스의 체가 캐시 효율성 때문에 더 빠를 수 있다.</ref>

=== 분할 체 (Segmented Sieve) ===
매우 큰 범위의 소수를 구할 때는 메모리 문제가 발생한다. 이때 '''구간을 나눠서''' 처리하는 방법이 분할 체다.

예: 10억~10억 1000만 사이의 소수를 구하려면?
1. <math>\sqrt{10^9}\approx 31623</math>까지의 소수를 먼저 구한다.
2. 이 소수들로 10억~10억 1000만 구간을 체로 거른다.
3. 메모리는 1000만개만 필요하다. (10억개가 필요하지 않다)

== 장단점 ==
=== 장점 ===
* '''매우 빠르다''': <math>O(N\log\log N)</math>은 거의 선형 시간
* '''구현이 간단하다''': 초보자도 쉽게 이해 가능
* '''직관적이다''': "배수를 지운다"는 개념이 명확함
* '''다목적''': 소수 판별, 소인수분해, 오일러 함수 등 다양하게 응용 가능

=== 단점 ===
* '''메모리를 많이 쓴다''': <math>O(N)</math> 공간 필요
* <math>N=10^9</math> 같은 큰 값에서는 메모리 부담이 커질 수 있다.
* '''한 번에 한 범위만''': 예를 들어 10억~20억번째 소수를 직접 구하려면 더 작은 범위를 포함해 넓게 처리해야 할 수 있다.
* 분할 체로 완화 가능
* '''매우 큰 소수''': <math>N</math>이 너무 크면 메모리 부족
* [[밀러-라빈 소수판별법]] 같은 확률적 방법 사용

== 실생활 활용 ==
=== 암호학 ===
[[RSA 암호]]에서 큰 소수를 찾을 때 사용된다. 물론 수백 자리 소수는 에라토스테네스로 직접 찾기 어렵고 확률적 방법을 쓰지만, 작은 소수를 미리 걸러낼 때 활용된다.

=== 프로그래밍 대회 ===
[[알고리즘 문제 해결 전략]]에서 빈출되는 기법이다. [[백준 온라인 저지]], [[코드포스]], [[프로젝트 오일러]] 등에서 자주 출제된다.

특히 [[프로젝트 오일러]]의 많은 문제들이 에라토스테네스의 체를 요구한다.

=== 수학 연구 ===
* '''골드바흐 추측''' 검증
* '''쌍둥이 소수''' 탐색
* '''소수 분포''' 연구
* '''리만 가설''' 실험

== 흥미로운 사실 ==
* '''2000년 이상 현역''': 기원전 240년에 만들어진 알고리즘이 현대에도 쓰인다.<ref>알고리즘 자체는 고전이지만, 구현과 최적화는 현대 하드웨어에 맞추어 계속 발전해 왔다.</ref>

* '''최초의 체계적 알고리즘?''': 수학사에서 가장 오래된 알고리즘 중 하나로 언급된다.

* '''이름의 유래''': 실제로 고대 그리스에서는 구멍 뚫린 파피루스에 숫자를 써서 합성수에 해당하는 구멍을 막는 방식으로 사용했다는 이야기가 전해진다.<ref>정확한 사료가 충분히 남아 있지 않아 전승 수준의 설명으로 다루어지는 경우가 있다.</ref>

* '''<math>10^{23}</math>까지 계산됨''': 현대 컴퓨팅으로 매우 큰 범위의 소수 관련 계산이 수행된 바가 있으나, 사용된 알고리즘은 문제에 따라 다양하다.

* '''메르센 소수는 예외''': <math>2^{82{,}589{,}933}-1</math> 같은 메르센 소수는 범위 체로 직접 탐색하기 어렵다. 이런 경우에는 [[뤼카-레머 판별법]] 같은 특수한 판별법을 쓴다.

== 교육적 가치 ==
에라토스테네스의 체는 '''알고리즘 교육'''에 매우 좋은 예시다:

1. '''최적화 사고''': 단순한 방법 → 개선된 방법으로의 진화
2. '''시간-공간 트레이드오프''': 메모리를 써서 시간을 아낀다
3. '''수학과 프로그래밍의 융합''': 수학적 성질을 코드로 구현
4. '''점진적 개선''': 짝수 건너뛰기, <math>i^2</math>부터 시작 등 단계적 최적화

많은 [[알고리즘]] 교과서에서 초반에 에라토스테네스의 체를 다루는 이유로 자주 언급된다.

== 비교: 다른 소수 판별 방법들 ==
{| class="wikitable"
! 방법 !! 시간 복잡도 !! 공간 복잡도 !! 특징
|-
| 시행 나눗셈 || <math>O(\sqrt{N})</math> || <math>O(1)</math> || 단일 수 판별에 적합
|-
| '''에라토스테네스의 체''' || '''<math>O(N\log\log N)</math>''' || '''<math>O(N)</math>''' || '''범위 내 모든 소수'''
|-
| 선형 체 || <math>O(N)</math> || <math>O(N)</math> || 이론상 최적, 구현 복잡
|-
| [[밀러-라빈]] || <math>O(k\log^3 N)</math> || <math>O(1)</math> || 확률적, 매우 큰 수
|-
| [[AKS 소수판별법]] || <math>O(\log^6 N)</math> || <math>O(\log N)</math> || 결정적, 이론적 의의
|}

== 관련 문제 ==
=== 백준 온라인 저지 ===
* [https://www.acmicpc.net/problem/1929 1929번: 소수 구하기] - 기본 문제
* [https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수] - 응용 문제
* [https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측] - 에라토스테네스 + 골드바흐

=== 프로젝트 오일러 ===
* Problem 10: 200만 이하 모든 소수의 합
* Problem 50: 가장 긴 소수 연속합

== 여담 ==
* 에라토스테네스는 이 알고리즘 외에도 '''지구 둘레 측정''', '''윤년 계산''', '''지리학 좌표계''' 등을 개발한 것으로 알려져 있다.
* '''체'''를 뜻하는 영어 "Sieve"는 밀가루를 거르는 체를 말한다. 실제로 밀가루 체와 작동 원리가 비슷하다.
* 이 알고리즘은 '''병렬화'''가 비교적 쉽다. 각 구간을 독립적으로 처리할 수 있어서 멀티코어 환경에서 효율적으로 구현될 수 있다.
* [[디리클레 정리]]를 이용하면 특정 등차수열 내의 소수만 골라내는 이론적 논의로도 확장할 수 있다.

== 관련 문서 ==
* [[소수(수론)]]
* [[에라토스테네스]]
* [[밀러-라빈 소수판별법]]
* [[알고리즘]]
* [[정수론]]
* [[골드바흐의 추측]]
* [[쌍둥이 소수]]
* [[메르센 소수]]
* [[오일러 파이 함수]]
* [[뫼비우스 함수]]

== 외부 링크 ==
* [https://www.acmicpc.net/problem/1929 백준: 소수 구하기]
* [https://oeis.org/A000040 OEIS: Prime numbers]

== 각주 ==
<references />

[[분류:알고리즘]]
[[분류:수학]]
[[분류:정수론]]
[[분류:소수]]
[[분류:고대 그리스 수학]]
[[분류:프로그래밍]]

에라토스테네스의 체 - 편집 역사

Gaon12: 시작