エラトステネスの篩の正当性

($\Leftarrow$) $n$ が $\le\sqrt n$ の素因数を持たないと仮定する。もし $n$ が合成数なら $n=ab$、$1<a\le b<n$ と書ける。このとき $a\le\sqrt n$(そうでなければ $a>\sqrt n$ かつ $b\ge a>\sqrt n$ となり $ab>n$ を強制し矛盾)であり、$a$ の最小素因数 $p$ は $p\le a\le\sqrt n$ を満たすので、$p$ は $n$ の $\le\sqrt n$ の素因数となり——仮定に矛盾する。よって $n$ はそのような分解を持たず、$n$ は素数である。

($\Rightarrow$) $n$ が素数なら、その正の約数は $1$ と $n$ のみであり、$p<n$ を満たすいかなる素数もそれを割り切らない。特に $p\le\sqrt n$ のものも割り切らない。

これらを合わせると2つの条件が同値であることが示され、これはまさに篩で用いられる終了条件である:$\sqrt N$ までのすべての素数を処理した後、$[2,N]$ の中でまだマークされていないものはすべて右辺を満たし、したがって素数である。