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

자연수,natural_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:

VeryGoodWiki