ルジャンドルの篩(包除原理による計数)

任意の整数 $a\in A$ が $P(z)$ と互いに素であるための必要十分条件は、$p<z$ を満たすいかなる素数でも割り切れないことである。各約数 $d\mid P(z)$(これらの素数の部分集合の無平方な積)について、$A=\{1,\ldots,x\}$ における $d$ の倍数の個数はちょうど $\lfloor x/d\rfloor$ である。

$p<z$ に対する事象「$p\mid a$」に関する包除原理により、$\mathcal P$ の中の少なくとも1つの素数で割り切れる $a\in A$ の個数は $\sum_{p<z}\lfloor x/p\rfloor - \sum_{p<q}\lfloor x/(pq)\rfloor + \sum_{p<q<r}\lfloor x/(pqr)\rfloor - \cdots$ であり、掛け合わせる素数の個数に応じて符号が交代する。この交代する符号は、対応する無平方な $d\mid P(z)$ のメビウス関数 $\mu(d)$ そのものである:$\mu(1)=1$、$d$ が $k$ 個の異なる素数の積のとき $\mu(d)=(-1)^k$。

したがって $\mathcal P$ の中の少なくとも1つの素数で割り切れる個数は $-\sum_{d\mid P(z),\,d>1}\mu(d)\lfloor x/d\rfloor$。これを $|A|=\lfloor x\rfloor=x$($d=1$ の項、$\mu(1)\lfloor x/1\rfloor=x$)から引くと $P(z)$ と互いに素な個数が得られる:$S(A,\mathcal P,z)=x-\sum_{d\mid P(z),d>1}\mu(d)\lfloor x/d\rfloor=\sum_{d\mid P(z)}\mu(d)\lfloor x/d\rfloor$。

最後に $z=\sqrt x+1$ とすると $\mathcal P$ はちょうど $\le\sqrt x$ の素数となる:これらすべてと互いに素な任意の $a\in[2,x]$ は $1$ であるか、または(上の定理により $\le\sqrt x$ の素因数を持たないので)$>\sqrt x$ の素数であるので、$S(A,\mathcal P,\sqrt x+1)=1+\big(\pi(x)-\pi(\sqrt x)\big)$ となり、主張の等式が得られる。