この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）
出典検索?: "エラトステネスの篩" ? ニュース ・ 書籍 ・ スカラー ・ CiNii ・ J-STAGE ・ NDL ・ dlib.jp ・ ジャパンサーチ ・ TWL（2019年6月）

エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がついている。
アルゴリズム2 から 120 までの数に含まれる素数を探すGIFアニメーション

指定された整数x以下の全ての素数を発見するアルゴリズム。このアニメーションでは以下のステップにそって 2 から 120 までの数に含まれる素数をさがしている。
ステップ 1

120要素の配列の1番目にfalseを、2番目以降に全てtrueを入れる。
ステップ 2

配列の先頭から順に走査し、trueの要素を見つけたらその添字pを素数リストに追加し、配列の p 2 {\displaystyle p^{2}} 以上のpの倍数番目をfalseにする。
ステップ 3

上記の篩い落とし操作を、走査している要素の添字がxの平方根に達するまで行う。
ステップ 4

最後までtrueだった要素の添字を素数リストに追加して処理終了。
具体例　x=120 の場合

配列の中身は、trueである添字がどれかを表記。残りは全てfalseである。
ステップ 1
配列={2から120まで}、探索リストの先頭値=2
ステップ 2-1
素数リスト={2}配列={3から119までの奇数}、探索リストの先頭値=3
ステップ 2-2
素数リスト={2,3}配列={2,3,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71,73,77,79,83,85,89,91,95,97,101,103,107,109,113,115,119}次の素数=5
ステップ 2-3
素数リスト={2,3,5}配列={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97,101,103,107,109,113,119}次の素数=7
ステップ 2-4
素数リスト={2,3,5,7}配列={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}次の素数=11
ステップ 3
次の素数が 120 = 10.954 ⋯ {\displaystyle {\sqrt {120}}=10.954\cdots } に達しているのでステップ4へ
ステップ 4
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}
理論的考察

エラトステネスの.mw-parser-output ruby.large{font-size:250%}.mw-parser-output ruby.large>rt,.mw-parser-output ruby.large>rtc{font-size:.3em}.mw-parser-output ruby>rt,.mw-parser-output ruby>rtc{font-feature-settings:"ruby"1}.mw-parser-output ruby.yomigana>rt{font-feature-settings:"ruby"0}篩（ふるい）は 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 ) = ∑ d ∣ P ( n ) μ ( d ) ( [ n d ] − [ n d ] ) {\displaystyle \pi (n)-\pi \left({\sqrt {n}}\,\right)=\sum _{d\mid P({\sqrt {n}})}\!\mu (d)(\left[{\frac {\,n\,}{d}}\right]-\left[{\frac {\sqrt {n}}{d}}\right])}

となる（ μ ( d ) {\displaystyle \mu (d)} はメビウス関数）。

より一般に、整数の集合A から、z 以下の素数の倍数全てを篩うとき、残る元の個数 S ( A , P ) {\displaystyle S(A,P)} は、 S ( A , P ) = ∑ d ∣ P ( z ) μ ( d ) 。 A d 。 {\displaystyle S(A,P)=\sum _{d\mid P(z)}\!\mu (d)\left|A_{d\,}\right|}

と表すことができる。ここで A d {\displaystyle A_{d}} は A の元で d で割り切れるもの全体の集合を表す。この定式化はルジャンドルの篩ともよばれる。

再び先の素数の個数の評価について述べれば、 z ≤ n {\displaystyle z\leq {\sqrt {n}}} のとき、不等式 π ( n ) − π ( z ) + 1 ≤ ∑ d ∣ P ( z ) μ ( d ) [ n d ] {\displaystyle \pi (n)-\pi (z)+1\leq \sum _{d\mid P(z)}\!\mu (d)\left[{\frac {\,n\,}{d}}\right]}