中1です。500以上1000以下の素数を３つ探し、

質問

中1です。500以上1000以下の素数を３つ探し、
それが素数であることを示してください。

それで、エラトステネスのふるいという方法を
教えてもらったのですが、
よくわからなかったので、
どなたかわかりやすく教えてください。

あと、まだルートを習っていないのでルートを使った式は
わかりません・・・。

宜しくお願いします。

回答No.2

sak_sak

素数は約数ととても近い関係にあることはわかりますね?
そこで、12の約数の探し方を思い出してみましょう。
まず1が挙げられますが、この時に12もセットにすると間違いが少ないですね。
同じように2と6をセットにして、3と4もセットにすれば終わりです。
12を1で割ったり、2で割ったり、3で割ったりはやるけれど
4で割ったり、5で割ったり、6で割ったりは実際上やってないですね。

37はどうでしょうか?
1と31、2はだめ、3もだめ、4もだめ、5もだめ、6もだめ
次は7になりますが、仮に7とセットになる数があったとしても、7より小さい数のはずだから、
1～6で割ったときに7が出てこなかったということは7では割り切れないということです。
この考え方がとても重要です。

これで37が素数であることがわかります。
37が素数かどうかをチェックするには6までやれば十分にわかるわけです。
7×7＝49が37より大きいから、という解釈もできます。

では、逆に考えてみましょう。
もし37以下の素数が全部わかったら
どこまでチェックが可能になるのでしょうか。
37×37＝1369だから、1369まで可能だということです。
つまり、あなたの目的達成のためには
37以下の素数でチェックするだけで十分だということになります。

ここまでの説明で十分に素数は求められると思いますが
エラトステネスの篩(ふるい)について説明します。

まずノートなどに500～1000の数を書き出してみましょう。
偶数で素数なのは2しかないので最初から奇数だけ書き出しても良いです。
面倒なら500～599の中に3個くらいは十分にありますから
それだけでもいいです。
ポイントはマス目を書いておくということです。
もし1行に10個ずつ書いていくとしたら
501,503,505,507,509,511,513,515,517,519,
521,523,525,527,529,531,533,535,537,539,
541,543,545,547,549,551,553,555,557,559,
561,563,565,567,569,571,573,575,577,579,
581,583,585,587,589,591,593,595,597,599,
…となります。

奇数しか書いてないですから2のチェックは必要ないので
3の倍数であるものは消していきます(×や斜線で)。
すると、501、507と525と543、515と533と551、539と557、というように
斜めの直線状に3の倍数が並んでいることがわかると思います。
同じように5の倍数、7の倍数、…37の倍数まで消していくのです。
思ったより早く終わると思いますよ。

消されずに残ったものが素数になります。