エラトステネスの篩（えらとすてねすのふるい）

概要

エラトステネスの篩（エラトステネスのふるい）は、古代ギリシャの数学者エラトステネスによって考案された素数判定アルゴリズムである。与えられた整数までの素数を効率的に見つけ出すことができる。

アルゴリズム

1. 2から指定された上限までの整数のリストを作成する。
2. 最小の素数である2を特定する。
3. 2の倍数をリストから削除する（2自身は除く）。
4. 次にリストに残っている最小の数（次の素数）を特定する。
5. その数の倍数をリストから削除する（その数自身は除く）。
6. リストに数が残っている限り、ステップ4と5を繰り返す。
7. 最終的にリストに残った数が素数となる。

計算量

エラトステネスの篩の計算量はO(n log log n)であり、n以下の素数を求める効率的なアルゴリズムの一つである。

歴史的背景

エラトステネスは、紀元前276年頃から紀元前194年頃に生きたギリシャの数学者、天文学者、地理学者である。彼はアレクサンドリア図書館で活躍し、地球の周囲を測定するなど、様々な業績を残した。エラトステネスの篩は、彼の数学的な才能を示す代表的な例である。

応用例

エラトステネスの篩は、素数判定だけでなく、暗号技術における鍵生成や、計算機科学における様々な問題に応用されている。