【素数の求め方】エラストテネスの篩(ふるい)がわかる5ステップ

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

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

 

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

だけど、

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

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

勘?? 運?? 電卓??・・・

 

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

エラトステネスのふるい(篩)

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

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

 

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

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

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

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

 

 

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

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

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

 

例として、

1から100までの素数

を求めてみよう!

 

 

 

Step1. 自然数をかきまくる

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

今回でいうと、

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

んだったね??

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

 

えっ。

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

そうだね。

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

ちょうどこんな感じ↓↓

 

 

eratosu1

 

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

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

 

 

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

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

えっ。

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

 

じつは、

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

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

 

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

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

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

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

100をこえちゃう。

 

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

  • 2
  • 3
  • 5
  • 7

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

 

erasuto6

 

これが第2ステップ!

 

 

Step3. 「1」を斜線でけす

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

赤でも緑でも構わない。

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

 

erastuto7

 

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

 

 

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

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

なぜなら、

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

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

 

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

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

 

erasuto7

 

おつぎは3の倍数。

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

 

erasuto10

 

つぎは5の倍数。

5の倍数は、

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

の2通りになるはず。

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

 

gonobai1

 

最後に7の倍数。

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

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

をけしてやろう!

erara1

 

 

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

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

 

erara2

 

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

素数

だ。

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

 

 

まとめ:エラストテネスの篩(ふるい)はあとから楽になる

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

簡単でわかりやすい。

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

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

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

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

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

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

そんじゃねー

Ken