Eratosthenesの篩

手順 2 で $p$ の段に来た時点（$p$ の番を行うかどうか決める直前）について、次の主張 $(\ast)_p$ を $p$ についての帰納法で示す。
$(\ast)_p$：$2\le m\le N$ について、$m$ が消えていることと、$m$ が「$q< p$ かつ $q^2\le m$ を満たす素数 $q$」で割り切れることは同値である。
$p=2$ の時点では何も消えておらず、$q<2$ となる素数もないので $(\ast)_2$ は成り立つ。$(\ast)_p$ を仮定する。
まず、$p$ の段で $p$ が残っていることと、$p$ が素数であることは同値である。実際 $(\ast)_p$ により、$p$ が消えていることは「$q< p$、$q^2\le p$ の素数 $q$ が $p$ を割る」ことと同値である。$p$ が素数ならそのような $q$ はない。$p$ が合成数なら、素数 の記事の命題「素因数の存在」により $p$ の最小の素因数 $q$ は $q\le\sqrt p$ を満たし、$q^2\le p$、$q< p$ である。
したがって $p$ の番が行われるのは $p$ が素数のときだけで、そのとき消されるのは $p^2,p^2+p,\dots$、すなわち「$p$ で割り切れて $p^2\le m$ を満たす $m\le N$」全体である。番を行わない（$p$ が合成数の）ときは何も変わらず、$p$ の段で新しく条件に加わる $q=p$ は素数でないので条件も変わらない。どちらの場合も $(\ast)_{p+1}$ が成り立つ。これで帰納法が完了し、1 が示された。
手順が終わるのは $p^2>N$ となる最初の $p$ の段であり、$(\ast)_p$ が成り立っている。$m\le N$ について $q^2\le m$ なら $q^2\le N< p^2$ から $q< p$ なので、終了時に $m$ が消えていることは「$q^2\le m$ を満たす素数 $q$ が $m$ を割る」ことと同値である。
2：$m$ が素数なら、$m$ を割る素数は $m$ だけで $m^2>m$ なので、$m$ は残る。$m$ が合成数なら、最小の素因数 $q$ が $q^2\le m$ を満たす（上と同じ命題）ので、$m$ は消える。
3：1 と上の議論により、$m$ は、$m$ を割り $p^2\le m$ を満たす素数 $p$ の番でちょうど 1 回ずつ消され、それ以外の番では消されない。
4：素数 $p\le\sqrt N$ の番で消す数は、$p^2$ から $N$ までの $p$ の倍数 $p\cdot p,p\cdot(p+1),\dots,p\cdot\lfloor N/p\rfloor$ であり、その個数は $\lfloor N/p\rfloor-p+1$ である。これを番が行われるすべての $p$（1 により $\sqrt N$ 以下の素数全体）について足せばよい。$\square$

左の不等式：thm-soe-sieve の 2 と 3 により、$2$ 以上 $N$ 以下の合成数 $N-1-\pi(N)$ 個はそれぞれ 1 回以上消されるからである。
中央の不等式：$p\ge1$ なので $\lfloor N/p\rfloor-p+1\le N/p$ であり、thm-soe-sieve の 4 の各項をこれで抑えればよい。
右の不等式：$y:=\sqrt N\ge2$ とおく。$y$ 以下の素数は $2$ 以上 $\lfloor y\rfloor$ 以下の整数の一部なので、調和級数 の記事の命題「積分による上下の評価」の $H_n\le1+\log n$（$H_n=\sum_{k=1}^n1/k$）を使って
$$ \sum_{p\le y}\frac1p\le\sum_{k=2}^{\lfloor y\rfloor}\frac1k=H_{\lfloor y\rfloor}-1\le\log\lfloor y\rfloor\le\log y=\frac12\log N $$
である。$\square$

次の主張 $(\dagger)_i$ を $i$ についての帰納法で示す。以下の「消される数の最小の素因数」と「各合成数はちょうど 1 回消される」の議論は、段 $i$ の操作について $(\dagger)_i$ だけを使うので、$(\dagger)_2,\dots,(\dagger)_i$ が示された範囲でそのまま使える。
$(\dagger)_i$：$i$ の段に来た時点で、$P$ は $i$ 未満の素数を小さい順に並べた列であり、$2\le m< i$ のすべてで $s[m]=\operatorname{lpf}(m)$ であり、$s[i]\ne0$ は $i$ が合成数であることと同値で、そのとき $s[i]=\operatorname{lpf}(i)$ である。
消される数の最小の素因数：どの段でも、2 で $s[pi]:=p$ とするとき、$p$ は素数で $p\le s[i]$ である。帰納法の仮定と 1 により $s[i]=\operatorname{lpf}(i)$ なので（$i$ が素数なら 1 で $s[i]=i$）、$p$ は $i$ のどの素因数以下でもあり、$p=\operatorname{lpf}(pi)$ である。つまり、消される数 $m=pi$ には必ず $s[m]:=\operatorname{lpf}(m)$ が書かれ、$pi\ge 2i>i$ なので、消されるのはいつもまだ段が来ていない数である。
帰納法：$(\dagger)_2$ は明らかである。$(\dagger)_i$ を仮定すると、$i$ の段の 1 で $s[i]=0$ なのは $i$ が素数のときちょうどであり、そのとき $i$ が $P$ に加わって $s[i]=i=\operatorname{lpf}(i)$ となる。$i$ が合成数なら $(\dagger)_i$ によりすでに $s[i]=\operatorname{lpf}(i)$ である。段 $i$ の 2 で書き換わるのは $pi>i$ の番号だけなので、$m\le i$ の $s[m]$ はこのあと変わらない。$i+1$ については、合成数なら次の段落により $i+1$ より前の段で消されて $s[i+1]=\operatorname{lpf}(i+1)$ となっており、素数なら $i+1=pi'$（$i'\ge2$）とは書けないので一度も消されず $s[i+1]=0$ である。よって $(\dagger)_{i+1}$ が成り立つ。
各合成数はちょうど 1 回消される：$m\le N$ を合成数、$q=\operatorname{lpf}(m)$、$i=m/q$ とする。素数 の記事の命題「素因数の存在」により $q^2\le m$ なので $i\ge q\ge2$ であり、$i$ の素因数はどれも $m$ の素因数なので $\operatorname{lpf}(i)\ge q$ である。$i$ の段では、$q\le i$ の素数 $q$ は $P$ に入っている（$q=i$ のときは同じ段の 1 で加わる）。2 で $P$ を小さい順にたどるとき、$q$ 以下の素数 $p$ はどれも $p\le q\le\operatorname{lpf}(i)=s[i]$ と $pi\le qi=m\le N$ を満たすので打ち切られず、$p=q$ で $m=qi$ が消される。逆に、ある段 $i'$ で素数 $p'$ によって $m=p'i'$ が消されたとすると、上で示したとおり $p'=\operatorname{lpf}(m)=q$ であり、$i'=m/q=i$ である。1 つの段で同じ $p$ は 1 回しか使わないので、$m$ が消されるのはちょうど 1 回である。素数は $pi$（$p,i\ge2$）の形に書けないので消されない。
終了後の主張は $(\dagger)_N$ と $N$ の段の操作から従う。$\square$

$m\in(M,Y]$ が素数なら、$m$ を割る素数は $m$ だけで、$m^2>m$ なので $m$ は $p^2\le m$ を満たす $p$ の倍数として消されることはない。$m$ が合成数なら、最小の素因数 $q$ は $q^2\le m\le Y$ を満たすので $q\le\sqrt Y$ であり、$m$ は $q^2$ 以上の $q$ の倍数として消される。$\square$