プログラミングを学んでいると、数学的なアルゴリズムに触れる機会が数多く存在します。
その中でも、特定の範囲から素数を効率よく見つけ出す手法として有名なのが「エラトステネスの篩（ふるい）」です。
このアルゴリズムは紀元前3世紀頃に古代ギリシャの数学者エラトステネスによって考案されました。
現代のコンピュータサイエンスにおいても、素数を列挙する際の最も基本的なアルゴリズムとして広く活用されています。
本記事では、エラトステネスの篩の仕組みから、プログラミングにおける実装方法、さらにはパフォーマンスを向上させるための最適化手法までを詳しく解説します。
エラトステネスの篩とは？
エラトステネスの篩は、指定された整数以下のすべての素数を抽出するための、古くから伝わる単純かつ高速なアルゴリズムです。
素数とは、1とその数自身以外に正の約数を持たない、2以上の自然数のことを指します。
例えば、2、3、5、7、11、13などが素数に該当します。
ある数が素数であるかどうかを一つずつ判定する「素数判定」とは異なり、範囲内にあるすべての素数をまとめて特定する際にこのアルゴリズムは真価を発揮します。
「篩（ふるい）」という名前が示す通り、この手法は合成数（素数ではない数）を次々と落としていき、最後に残ったものが素数であるという考え方に基づいています。
プログラミングの分野では、競技プログラミングや暗号理論の基礎、数学的なシミュレーションなどで頻繁に使用されます。
アルゴリズムの仕組みと手順
エラトステネスの篩がどのように動作するのか、その具体的な手順を追いながら解説します。
例えば、1から30までの数字の中から素数を探し出す場合を想定してみましょう。
まず、1は定義上素数ではないため、あらかじめ除外しておきます。
残った数字の中で最小の数は「2」であり、これは素数であることが確定します。
次に、確定した素数「2」の倍数をすべてリストから消去します。
2の倍数である4、6、8、10……30は、2を約数に持つため、素数ではないことが確定するためです。
次に残っている最小の数は「3」であり、これも素数として確定させます。
同様に、3の倍数である6、9、12、15……を消去していきますが、すでに消されている数（6や12など）はスキップして構いません。
次に残った最小の数は「5」ですので、5を素数とし、その倍数である10、15、20……を消去します。
この作業を、「探索範囲の最大値の平方根（ルート）」まで繰り返します。
今回の例である30までの探索であれば、√30は約5.47ですので、5までの倍数を確認すれば十分です。
なぜ平方根までで良いのかというと、それ以上の数の倍数はすでにこれまでの工程で消去されていることが数学的に証明されているからです。
最終的にリストに残った数字が、その範囲内にあるすべての素数となります。
エラトステネスの篩のメリット
素数を見つける方法は他にもいくつかありますが、エラトステネスの篩がなぜ優れているのかを説明します。
計算効率の高さ
最も単純な素数判定法として、ある数nを2からn-1までの数で順番に割ってみる「試し割り法」があります。
しかし、範囲内のすべての数に対して試し割りを行うと、計算量は非常に膨大なものになってしまいます。
エラトステネスの篩の計算量は、O(N log log N)という極めて優れた効率を誇ります。
これは、探索範囲Nが大きくなっても計算時間が急激に増えにくいことを意味しており、大規模な数値範囲でも実用的に動作します。
実装の単純さ
アルゴリズムの仕組みが視覚的で分かりやすいため、プログラミング言語を問わず簡単に実装できる点も魅力です。
真偽値（boolean）の配列を用意し、倍数にフラグを立てていくだけの処理で構成できます。
複雑な数学関数を必要としないため、低レイヤーの言語からスクリプト言語まで幅広く対応可能です。
プログラミングにおける実装例
実際に、汎用的なプログラミング言語であるPythonを使用して、エラトステネスの篩を実装してみましょう。
以下のコードは、指定された数nまでの素数をリスト形式で返す関数です。
def sieve_of_eratosthenes(n):
# すべての数について素数判定フラグをTrueで初期化
# 0と1は素数ではないため、便宜上Falseとしておく
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
# 2から√nまで順番に判定を行う
for p in range(2, int(n**0.5) + 1):
# pが素数である場合
if is_prime[p]:
# pの倍数をすべてFalse（合成数）に更新
# p*pから開始することで重複を避ける
for i in range(p * p, n + 1, p):
is_prime[i] = False
# Trueのまま残っているインデックスを素数として抽出
primes = [i for i, prime in enumerate(is_prime) if prime]
return primes
# 50までの素数を求めて表示
result = sieve_of_eratosthenes(50)
print(result)このコードを実行すると、以下の結果が得られます。
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]コードのポイントは、内側のループにおいてp * pから開始している点です。
p * 2やp * 3などは、すでにそれより小さな素数の倍数判定の段階で処理されているため、ここから始めることで無駄な計算を省くことができます。
アルゴリズムの計算量と比較
エラトステネスの篩がどれほど高速なのか、他の代表的な手法と比較してみましょう。
| 手法名 | 時間計算量（Nまでの列挙） | 主な特徴 |
|---|---|---|
| 試し割り法（単純） | O(N^2) | 実装は最も簡単だが、非常に遅い |
| 試し割り法（√Nまで） | O(N√N) | 個別の判定には向くが、範囲列挙には不向き |
| エラトステネスの篩 | O(N log log N) | 非常に高速で、バランスが良い |
| アトキンの篩 | O(N / log log N) | さらに高速だが、アルゴリズムが複雑 |
表を見ると分かるように、エラトステネスの篩は単純な試し割り法に比べて圧倒的に効率的です。
「アトキンの篩」のようなさらに高度な手法も存在しますが、実装のしやすさと速度のバランスから、一般的にはエラトステネスの篩が最も推奨されます。
実装時のメモリ消費に関する注意点
エラトステネスの篩を実装する際、唯一とも言える弱点がメモリ使用量です。
このアルゴリズムは探索範囲の最大値Nと同じサイズの配列をメモリ上に確保する必要があります。
例えば、Nが1億（10^8）といった非常に大きな数になると、単純なboolean配列であっても100MB以上のメモリを消費することがあります。
一般的なPCであれば問題になりませんが、メモリ制限の厳しい組み込みシステムや、さらに大きな範囲を扱う場合には工夫が必要です。
メモリを節約するための一つの手法は、「ビットセット（Bitset）」を利用することです。
通常のboolean型は1つにつき1バイト（8ビット）を消費することが多いですが、ビットセットを使えば1つの数を1ビットで表現できるため、メモリ消費を約8分の1に抑えることができます。
また、偶数をあらかじめ除外して奇数のみを配列で管理すれば、さらに必要なメモリを半分に減らすことが可能です。
効率をさらに高めるための最適化手法
プログラミング視点でのさらなる最適化についていくつか紹介します。
奇数のみを扱う実装
2以外の偶数は決して素数にはならないため、最初から配列から除外しておくことができます。
これにより、配列のサイズを半減させ、計算の反復回数も半分に削減できます。
メモリ効率が向上するだけでなく、キャッシュヒット率が高まるため、実行速度の向上も期待できます。
セグメント化された篩（Segmented Sieve）
メモリ消費の課題を解決するための高度な手法として「セグメント化された篩」があります。
これは、探索範囲を小さな「セグメント」に分割し、セグメントごとに篩にかける方法です。
これにより、一度にメモリ上に保持する配列のサイズを抑えつつ、大きな範囲の素数を求めることが可能になります。
この手法は、数テラバイトクラスの巨大な範囲を探索する際や、並列処理（マルチスレッド）を行いたい場合に非常に有効です。
エラトステネスの篩が使われるシーン
このアルゴリズムは、どのような場面で具体的に役立っているのでしょうか。
競技プログラミング
AtCoderやLeetCodeといった競技プログラミングにおいて、素数に関する問題は定番のテーマです。
「10^6以下の素数の個数を求めよ」といった問題が出た際、愚直に判定していては時間制限（TL）に間に合いません。
エラトステネスの篩を素早く実装できることは、競技プログラマーにとって必須のスキルと言えます。
数学の研究と暗号の基礎
現代のインターネットを支える公開鍵暗号（RSA暗号など）は、巨大な素数の性質を利用しています。
実際に暗号で使用されるのは非常に桁数の多い巨大な数であるため、エラトステネスの篩をそのまま使うわけではありません。
しかし、アルゴリズムの基礎となる「素数の性質を利用した効率的な計算」という考え方は、暗号理論のあらゆる場所に応用されています。
素因数分解の高速化
単一の数ではなく、大量の数をまとめて素因数分解したい場合、事前にエラトステネスの篩を使って「最小の素因数」を記録したテーブルを作成しておく手法があります。
これを利用すると、各数に対してlog Nの速さで素因数分解を行うことができ、データ解析や数論の計算において極めて強力な武器となります。
まとめ
エラトステネスの篩は、紀元前から存在する古いアルゴリズムでありながら、現代のプログラミングにおいても現役で活躍し続けています。
「範囲内の素数を効率的に抽出する」という目的において、これほど完成された手法は他に類を見ません。
本記事で紹介した通り、その仕組みはシンプルですが、計算量への理解やメモリへの配慮など、プログラミングに必要なエッセンスが凝縮されています。
初心者の方はまず基本的な実装をマスターし、中級者以上の方はセグメント化やメモリ最適化に挑戦してみると良いでしょう。
アルゴリズムを深く理解することは、単に効率の良いコードを書くためだけでなく、コンピュータがどのようにデータを処理すべきかを考える力を養うことにも繋がります。
ぜひ、実際に自分の手でコードを書き、その驚異的なスピードを体感してみてください。
