'''에라토스테네스의 체, sieve of Eratosthenes'''

[[자연수,natural_number]]를 다음 둘로 분리하는 방법.
 * [[합성수,composite_number]]
 * [[소수,prime_number]]

특정 수의 primality(소수 여부)를 판단하기보다는 일정 [[범위,range]]내의 모든 수들에 대해 primality를 판단하여 양분하는 데 적합한 방법 ..?
특정 수의 판단에는 더 적합한 방법이 있을텐데 MKLINK -> primality_test

= 기초 사실 =
만일 $n$ 이 [[합성수,composite_number]]라면, [[약수,divisor]](인자)가 존재하고, 그 약수의 [[제곱,square]]은 $n$ 보다 크지 않다.
가정:
 $n=ab,\;\;a,b\in\mathbb{N}$
그러면 다음이 성립.
 $n^2=a^2b^2$
따라서 $a^2\le n$ 또는 $b^2\le n$ 이다.
(그렇지 않으면 $a^2>n$ 이고 $b^2>n$ 이 되어 $a^2b^2>n\cdot n=n^2$ 이 된다)
그래서 합성수 $n$ 과 약수 $d$ 의 관계는 다음과 같다.
 $d^2\le n$ 
 $d\le\sqrt{n}$
i.e.
 $n$ 의 약수 $d$ 는 $\sqrt{n}$ 보다 클 수 없다.
에라토스테네스의 체를 명제로 나타낸다면
 합성수 $n$ 은 $d\le\sqrt{n}$ 을 만족하는 약수 $d$ 를 갖는다.
(10개의 특강으로 끝내는 수학의 기본 원리)

----
Twins:
[[https://terms.naver.com/entry.naver?docId=3405213&cid=47324&categoryId=47324 수학백과: 에라토스테네스의 체]]
[[Wiki:SieveOfEratosthenes]]
[[Wiki:SieveOfEratosthenesInManyProgrammingLanguages]]

[[Libre:에라토스테네스의_체]]
https://rosettacode.org/wiki/Sieve_of_Eratosthenes

분류 ... [[정수론,number_theory]] [[알고리듬,algorithm]] ?
[[체,sieve]]
{
[[WpKo:체_(수론)]]
}