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

こんにちは！この記事をかいているKenだよ。中華は鉄板だね。

 

素数は何かってなんとなくわかった。

だけど、

どうやって素数を求めればいいんだろう？？

正直、求め方がわからない。

勘？？　運？？　電卓？？・・・

 

じつは素数の求め方の1つに、

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

っていう方法があるんだ。

ちょっと正直、ひびきがうさんくさいね。

 

だけど、使い方をおぼえるとチョー便利だから、

「エラストテネスのふるい」を5ステップでつかってみよう。

これをマスターすれば大丈夫。

素数を1発で求められるよ！

 

 

エラストテネスのふるい（篩）の使い方がわかる5ステップ

5ステップで素数を求めていくよ。

1. 　自然数をかく
2. 　はじめらへんの素数に○をつける
3. 　「1」を斜線で消す
4. 　「○をつけた素数の倍数」を斜線で消す
5. 　残ったやつが「素数」

 

例として、

1から100までの素数

を求めてみよう！

 

 

 

Step1.　自然数をかきまくる

求めたい範囲の自然数をかいてみよう。

今回でいうと、

1から100までの素数を求めたい

んだったね？？

だから、1から100までの自然数をかけばいいのさ。

 

えっ。

自然数のかきかたがわからんって？？

そうだね。

1行あたりに10個の自然数をかいてみて。

ちょうどこんな感じ↓↓

 

 

 

手が疲れるかもしないけど、ここが一番きついとこ。

歯をくしいばって自然数をかいてみよう。

 

 

Step2. 　最初のほうの素数に○をつける

最初のほうの素数に○をつけよう。

えっ。

どこまでの素数に○つければいいのかって？？

 

じつは、

2乗しても範囲をこえない素数

まで○でかこえばいいんだ。

 

1から100までの自然数にふくまれる素数だったら、

範囲でいちばん大きいのは100でしょ？？

2乗しても100をこえない最大の素数は「7」だね。

なぜなら、つぎの素数の「11」は2乗すると「121」になるからね。

100をこえちゃう。

 

だから、7までの素数の、

• 2
• 3
• 5
• 7

の4つを○でかこうんだ。

 

 

これが第2ステップ！

 

 

Step3. 「1」を斜線でけす

左上の「1」を斜線でけそう。

赤でも緑でも構わない。

とにかく、消してやろう。

 

 

1は素数じゃないから消すんだ。

 

 

Step4. ○つけた素数の倍数をけす！

今度は○がついてる素数の倍数をけすよ。

なぜなら、

「素数の倍数」は素数じゃないからね。

「1」と「自分」以外でも割れちゃうようになるもん。

 

例題でいうと、まず「2」の倍数をけしてやる。

偶数をぜーんぶ消すんだ。

 

 

おつぎは3の倍数。

斜めにしゅーっと線をひいてあげよう。

 

 

つぎは5の倍数。

5の倍数は、

• 1の位が「5」
• 1の位が「0」

の2通りになるはず。

だから「5」と「10」の下の数字たちはみーんな消されちゃう。

 

 

最後に7の倍数。

100以下で7の倍数になっている、

• 7
• 14
• 21
• 28
• 35
• 42
• 49
• 56
• 63
• 70
• 77
• 84
• 91
• 98

をけしてやろう！

 

 

Step5. 残った数を○でかこう

最後まで生き残った自然数を○でかこってみて。

 

 

○がついたぜーんぶの自然数が、

素数

だ。

どう？ 案外簡単でしょ？？

 

 

まとめ：エラストテネスの篩（ふるい）はあとから楽になる

エラストテネスの篩はちょー便利。

簡単でわかりやすい。

ただ、ちょっと残念なのが、

最初に自然数をたくさんかくところだ。

もし、1から1000までの素数を求めなきゃいけなかったら、

1000個の自然数をかかなきゃいけない。ゼッタイに手が震えるね。

でも、最初さえ乗り切れればあとは楽になる。

エラストテネスのふるいでガンガン素数を求めていこう！

そんじゃねー

Ken