エラトステネスの篩
11以上の、trueである要素の添字を素数リストに追加
素数リスト={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113}
エラトステネスの篩は x 1 / 2 {\displaystyle x^{1/2}} 以下の素数が既知のとき、( x 1 / 2 {\displaystyle x^{1/2}} 以上)x 以下の素数を決定するには、x 以下の整数で x 1 / 2 {\displaystyle x^{1/2}} 以下の素数の倍数を全て取り除けば(= 篩えば)よいことを意味する。このことから、包除原理を用いることによって x 以下の素数の個数に関する式を得ることができる。
具体的な式を書くために、いまx 以下の素数の個数を π ( x ) {\displaystyle \pi (x)} と書き、z 以下の全ての素数の積を P = P ( z ) {\displaystyle P=P(z)} とすると、この篩の操作が与える定量的な公式は
π ( n ) − π ( n ) + 1 = ∑ d ∣ P ( n ) μ ( d ) [ x d ] {\displaystyle \pi (n)-\pi \left({\sqrt {n}}\,\right)+1=\sum _{d\mid P({\sqrt {n}})}\!\mu (d)\left[{\frac {\,x\,}{d}}\right]}
となる(左辺の +1 は篩われずに残る数 {1} の分で、 μ ( d ) {\displaystyle \mu (d)} はメビウス関数)。
より一般に、整数の集合A から、z 以下の素数の倍数全てを篩うとき、残る元の個数 S ( A , P ) {\displaystyle S(A,P)} は、