エラトステネスのふるい とは

エラトステネスの篩（ふるい）とは？

エラトステネスのふるいは、自然数の中から素数を見つけるための方法です。素数とは 1 と自分自身以外に約数を持たない自然数のことです。

エラトステネスのふるいは、自然数を順に調べ、素数である場合はその倍数を取り除くという手順を繰り返します。この方法を使うことで、効率的に素数を見つけ出すことができます。

エラトステネスのふるいで50までの素数を見つけよう

例えば50以下の素数を全て求めてみましょう。下の図のように1から50までの数を書き、1から順に素数でないものを消していきます。素数以外の数をふるいにかけて落とすイメージです。

まず 1 は素数でないから消します。次に最初の素数2を残し、2の倍数（4, 6, 8, … 50）を全て消します。これらは2を約数として持つので素数ではありません。

次に進むと3に出会います。3は素数なので残し、3の倍数を全て消します。

次に進むと5に出会います。5は素数なので残し、5の倍数を全て消します。

この操作を続けると以下の数が消されずに残り、素数を見つけることができます。

2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47

これは、手続きつまりアルゴリズムです。素数は近世に入ってから数学者の注意を引き、数論という分野を作るもとになりました。しかし素数の研究は純粋に理論のためだけのもので、なんの役にも立たないと思われていました。素数が大勢の人の注目を集めるようになったのは、20世紀に入ってコンピュータが発達したおかげです。現代ではコンピュータのセキュリティの保護のために素数はなくてはならないものになっています。エラトステネスのふるいは、大きな素数表を必要とする素数の研究者にとっては貴重なものでした。

このアルゴリズムにはエラトステネスの名前がついていますが、素数の研究が盛んになった後世の誰かがエラトステネスの名前を割り当てただけかもしれません。

素数に関する解説はこちら▼

名前の由来となったエラトステネスとは

エラトステネスは古代ギリシア天文学者でアレクサンドリアの図書館長をしていました。地球の周長を測定したと言われています。