【アルゴリズム】素数をあぶり出す！「エラトステネスのふるい」｜情報処理問題1000本ノック

プログラミングの基礎問題としても頻出の「素数判定」。その中でも、特定の範囲から素数をまとめて探し出す効率的なアルゴリズムを攻略しましょう。

1. 問題：素数抽出のアルゴリズム

【 問題 】 指定された整数以下のすべての素数を効率的に見つけるための手法で、2から順にその倍数を消去していく（ふるい落とす）ことで素数だけを残すアルゴリズムを何と呼ぶでしょうか？

ア、エラトステネスのふるい   イ、遺伝的アルゴリズム   ウ、アリストテレスのアルゴリズム   エ、ピタゴラスの定理

2. 正解：アルゴリズムの基礎に関する正解

正解： ア、エラトステネスのふるい

3. 解説：倍数を消して素数を残す

エラトステネスのふるいは、紀元前3世紀にギリシャの数学者エラトステネスが考案した、非常にシンプルで高速な素数抽出法です。

【図解：エラトステネスのふるいの手順】

1. 初期状態
・2から目的の数（例：30）までの整数を並べます。

2. 倍数の消去
・「2」は素数として残し、2の倍数（4, 6, 8...）をすべて消します。
・次に残っている最小の数「3」を素数とし、3の倍数（9, 12...）を消します。
・これを繰り返し、最後に残ったものがすべて素数となります。

3. 終了条件
・探索する範囲の最大値の平方根（√n）まで調べれば、すべての素数が確定します。

[ 関連用語の整理 ]
★ 計算量：一つ一つ素数判定を行うより圧倒的に速く、O(n log log n)という非常に優れた効率を誇ります。
★ 遺伝的アルゴリズム：生物の進化を模倣して最適解を探る手法であり、素数判定とは無関係です。
★ 素数：1とその数自身でしか割り切れない、1より大きい自然数。

1. 理解のコツ: 「倍数は素数ではない」という性質を利用して、まるで「ふるい」にかけるように不純物（合成数）を取り除いていくイメージです。名前が似ている「アリストテレス（哲学者）」などに惑わされないようにしましょう。
2. 試験対策の視点: アルゴリズムの名称だけでなく、その具体的な手順（倍数を消していく）や効率性について問われることもあります。プログラミング試験でも実装例としてよく取り上げられるテーマです。

---

4. まとめ

「2から順に倍数を消去し、素数を抽出する」。これがエラトステネスのふるいです。数千年前の知恵が、現代のコンピュータ・プログラムにおいても現役で使われている非常に重要なアルゴリズムであることを押さえておきましょう。