エラトステネスのふるいで素数を求める

素数を求める方法として、最も有名なアルゴリズムが「エラトステネスのふるい」です。

エラトステネスのふるいの考え方

このアルゴリズムは、ある数以下の素数を求めるための代表的なアルゴリズムで、基本的な発想は「倍数を除いていく」というものです。

たとえば100以下の素数を求めるなら、まず1-100までの数字をすべてふるいに入れます。そしてそこから2の倍数、4,6,8,10…を除いていきます（ふるい落とす）。2自身は素数として取り分けておきましょう。次に3に対しても同様に9,15…を除きます（6や12は既に除かれている）。

4は既に除かれているので、次は5に対して同様の処理を行います。これを100の平方根である10まで繰り返すわけです。これで、ふるいには倍数とならなかった素数のみが残るので、取り分けておいた素数とあわせて素数表が完成しました。

このように、エラトステネスのふるいは倍数を次々にふるい落とすことで「自身と1以外の約数を持たない」素数を抽出するアルゴリズムです。

「素数の性質（定義）」をそのまま力技で「実現」するようなアルゴリズムですから、エラトステネスのふるいで素数の一覧（素数表）を作成するプログラムもごく単純なコードで実装できます。

巨大な数の素数を求めるのは難しい（メモリと計算量の制約）

ただエラトステネスのふるいのアルゴリズムを素直にプログラムとして実装すると、「ふるいにかける数をすべて格納するメモリ」が必要です。特に、100億単位になると32ビット（最大42億通り）では格納できませんので、1つの数字を64ビット（8バイト）で処理することになるでしょう。100億の数字を格納するとなると、それだけで800億バイト（80GB）です。

大きな素数表を作る際は、適当に分割するなどの対応が必要でしょう。そして、この「大きな素数表を作るためには、膨大なメモリや処理時間が必要」という素数を求めることの「難しさ」が、暗号の基礎にもなっているわけです。