エラトステネスの篩
π ( n ) ≤ π ( z ) + ∑ d ∣ P ( μ ( d ) n d + 1 ) = π ( z ) + n ∑ d ∣ P μ ( d ) d + ∑ d ∣ P 1 = π ( z ) + n ∏ p ≤ z ( 1 − 1 p ) + 2 π ( z ) {\displaystyle \pi (n)\,\leq \,\pi (z)+\sum _{d\mid P}\left(\mu (d){\frac {\,n\,}{d}}+1\right)\,=\,\pi (z)+n\sum _{d\mid P}{\frac {\mu (d)}{d}}+\sum _{d\mid P}1\,=\,\pi (z)+n\prod _{p\leq z}\left(1-{\frac {1}{\,p\,}}\right)+2^{\pi (z)}}
という評価が得られる。この公式から( z = log  n {\displaystyle z=\log n} とおき、素数の逆数の和が発散することを用いて)
lim x → ∞ π ( x ) x = 0 {\displaystyle \lim _{x\to \infty }\!{\frac {\,\pi (x)\,}{x}}=0}
を証明することができる。
しかし、其評価の過程で上の 2 π ( z ) {\displaystyle 2^{\pi (z)}} のような大きな誤差項が現れてしまうのは、包除原理にのみに依拠した式の共通の欠点である。このような困難を回避し、より一般的な状況で篩われた集合の元の個数を近似・評価するのが現代の篩法である。この方法は双子素数予想など、多くの数論上の問題の研究に広く応用されている。
指定された整数x以下の全ての素数を発見するアルゴリズム。このアニメーションでは以下のステップにそって 2 から 120 までの数に含まれる素数をさがしている。
素数リスト={2}
配列={3から119までの奇数}、探索リストの先頭値=3