エラトステネスの篩【sieve of Eratosthenes】

概要

エラトステネスの篩（sieve of Eratosthenes）とは、与えられた整数以下の素数をすべて発見する計算手順(アルゴリズム)の一つ。素数判定法の一種で、古代ギリシャの学者であるエラトステネス(Eratosthenes)が紀元前3世紀頃に考案したとされるため、このように呼ばれる。

まず、2から目的の数までの整数のリストを用意する。このリストの中から最初の素数である2の倍数を消していく。リストに残った整数のうち、先頭にある3が次の素数である。次に、リストの中から3の倍数を消してゆき、残った整数のうち先頭にある5が次の素数である。

このように、先頭に残った数の倍数をリストから消してゆき、その都度先頭に残った数を集めると、素数のリストが得られる。このアルゴリズムが「篩」（ふるい）と呼ばれるのは、この一連の操作が、粉状のものを何段階もふるいにかけてより分ける作業に似ていることに由来する。

この操作は目的の数まで繰り返す必要はなく、先頭に残った素数の2乗が与えられた数を超えるまで（先頭の素数が目的の数の2乗根を超えるまで）でよい。これ以降にリストに消されずに残っている数はすべて素数である。整数においては $a \times b = b \times a$ が成り立つため、これ以降に存在する合成数はそれ以前の操作によりすべて消されているためである。

(2024.5.20更新)