【アルゴリズム】数字をふるい落として素数をあぶり出す！「エラトステネスのふるい」｜情報処理問題1000本ノック
アルゴリズムの歴史の中でも最古にして、今なお基本として学び継がれる美しい手法。指定された範囲から素数だけを効率よく見つけ出すメカニズムを攻略しましょう。
1. 【 問題 】：素数探索のアルゴリズム
【 問題 】 コンピュータのアルゴリズムや数学において、指定された整数以下のすべての素数を効率よく見つけ出すための代表的なアルゴリズム（計算手順）はどれでしょうか？
（ア）エラトステネスのふるい
（イ）遺伝的アルゴリズム
（ウ）アリストテレスのアルゴリズム
（エ）ピタゴラスの格差定理
2. 正解：
正解： （ア）エラトステネスのふるい（Sieve of Eratosthenes）
3. 解説：倍数をまとめて「消去」していく快感
エラトステネスのふるいは、古代ギリシャの数学者エラトステネスが考案した、特定の範囲内にある素数をすべて見つけ出すための非常にシンプルなアルゴリズムです。
1. まず、1から30までの数字をずらりと並べます（「1」は素数ではないので最初から除外します）。
2. まだ消されていない最小の数「2」を見つけます。これが最初の素数です。そして、2以外の「2の倍数（4, 6, 8...）」をすべて表から消去（ふるい落とす）します。
3. 次に残っている最小の数「3」を見つけます。これが2番目の素数です。そして、3以外の「3の倍数（9, 15, 21...）」をすべて消去します（6や12はすでに2の段階で消えています）。
4. 次に残っている最小の数「5」を見つけ、同様に5以外の「5の倍数」をすべて消去します。
→ このように「素数を見つけたら、その倍数を一網打尽に消していく」という操作を繰り返すことで、最後まで残った数字がすべて素数になります。 ← ココが問題の正解！
★ （イ）遺伝的アルゴリズム（GA）：生物の進化（交配・突然変異・自然淘汰）の仕組みを模倣して、最適解を探索するAI分野などの高度なアルゴリズムです。素数の特定とは関係ありません。
★ （ウ）アリストテレスのアルゴリズム：アリストテレスは有名な古代ギリシャの哲学者ですが、このようなアルゴリズムは存在しない架空の選択肢です。
★ （エ）ピタゴラスの格差定理：「三平方の定理（ピタゴラスの定理）」で有名な数学者ですが、こちらも問題に合わせたもっともらしい架空の用語です。
1. 理解のコツ: 「パスタの湯切り（水切り）」をイメージしてください。水（合成数＝他の数で割り切れる数字）と、具材（素数）が混ざった鍋をザル（ふるい）に流し込みます。2の倍数を流し、3の倍数を流し……と、余計な倍数たちをどんどん下に落としていくと、ザルの上には「絶対に他の数では割り切れない硬い素数だけ」が綺麗に残ります。だからエラトステネスのふるいと呼ばれています。
2. 試験対策の視点: 「素数を見つけるアルゴリズム」「ふるい」というキーワードを見たら迷わずエラトステネスのふるいを選択してください。ITパスポートから基本情報、応用情報試験の午前問題では、プログラミングの基本アルゴリズム（繰り返し処理や配列の操作）を学ぶための王道テーマとして非常によく出題されます。
4. まとめ
「指定された整数までの数字から、既知の素数の倍数を順番に消去していくことで、効率的に素数だけを抽出する古典的アルゴリズム」。これがエラトステネスのふるいです。1つずつ割り切れるか確かめる地道な方法に比べて、倍数をまとめて消していけるため圧倒的に計算量が少なく、コンピュータに素数のリストを作らせる際のお手本として今なお愛されています。