エラトステネスの篩とは、素数を見つけるためのアルゴリズムの一つである。
まず、2から始めて2の倍数を全て除外する。次に、残った数の中で最小の数である3を残し、3の倍数を除外する。同様に、残った数の中で最小の数である5を残し、5の倍数を除外する。これを繰り返すことで、素数のみが残った数列を得ることができる。
以下に、具体的な例を示す。
- まず、2から始める。
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...
- 2の倍数を除外する。
2, 3, , 5, , 7, , 9, , 11, , 13, , 15, , 17, , 19, , ...
- 残った数の中で最小の数である3を残し、3の倍数を除外する。
2, 3, , 5, , 7, , , , 11, , 13, , , , 17, , 19, , ...
- 残った数の中で最小の数である5を残し、5の倍数を除外する。
2, 3, , 5, , 7, , , , 11, , 13, , , , 17, , 19, , , 23, , ...
- 同様に繰り返すことで、素数のみが残った数列を得ることができる。
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, ...
エラトステネスの篩の特徴は、素数の個数が多い場合でも比較的効率的に素数を求めることができることである。また、プログラム化も容易であるため、コンピュータサイエンスにおいても広く利用されている。