エラトステネスのふるい｜素数を洗い出す古典的手法！

プロローグ

こんにちは、博士！

こんにちは。今日は学校でどんなことをしたんじゃ？

今日は算数で素数を勉強したよ！

約数が１とその数字だけとなる数字だね。

ふむ。具体的にはどんな数だったかの。

２、３、５、７、１１、１３・・・、１７、・・・２３？

ふぉっふぉっふぉ。何やら不安そうじゃの。

それでは、素数を見つける簡単な方法を学んでみようかの！

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

どの数字が素数か知りたくなること、ありますよね(無理やり(笑))！

【エラトステネスのふるい】は、素数を見つけ出す簡単で単純な方法です。

実際の手順を以下に示していきます。今回は１～５０の数字から素数を見つけていきます。

①：２の倍数に印をつけていく。

初めに、最も小さな素数である２とその倍数(２，４，６・・・)に印をつけていきます。

ここで、基準となる２には〇をつけておきます。

※素数の定義から、１は素数ではないので注意！

すると、以下のようになります。

②：3の倍数に印をつけていく。

次に、印のついていない数字の中で一番小さい数字(1は除く)である、

３とその倍数(３，６，９・・・)に印をつけていきます。

ここで、基準となる３には〇をつけておきます。

すると、以下のようになります。

③5の倍数・７の倍数にも同様に印をつけていく。

以降、印のついていない数字(５，７)を基準に取り印をつける作業を繰り返していきます。

このとき、表の最大の数字に注目し、

表の最大数≦次に調べる素数の二乗

となっていたらそれ以上調べる必要はありません。

今回の例では、７まで調べた時点で以下のような表が得られます。

次に調べるのは印のついていない１１になるわけですが、これは、

５０≤１１²＝１２１

という式が成り立つため、これで数え上げは終了です。

④：印のついていない数字について〇をつける。

すると、以下のような表が得られます。

お疲れさまでした！この表で、丸印で囲まれた数字が１から５０までの数字に存在する素数です！

この方法はすこし手間に思うかもしれませんが、

数字が大きくなっていっても同様に数え上げることで素数を求めることができます。

エピローグ

これならどれが素数か忘れちゃっても導けるね！

そうじゃな。

数字を素数の”ふるい”にかけて、残ったものが求めていた素数群になるわけじゃ。

ところで、博士が最近”ふるい”にかけたものってなあに？

最近、古い友人から突然連絡がきたんじゃよ。

久しぶりに会おうっていうので楽しみにして行ってみたんじゃがーー。

・・・いや、この話は悲しくなるからもうやめるんじゃ・・・。

・・・、なんかごめんね、博士。