中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の倍数まで消していくのです。
思ったより早く終わると思いますよ。

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

回答No.1

Kules

エラトステネスのふるいですか…
私もちょっとうろ覚えなんですが、結局何か整数の倍数になってるものは素数なわけないんだから、それを取り除いていけば残った数字は素数なんじゃね？ってやつですよね？

例えば500～1000というと501個の数字がありますが、その中で偶数は素数なわけない(２の倍数だから)251個しか考える必要はないですよね？
で、３の倍数も違う→５の倍数も違う→７の倍数も違う、ぐらいでふるいにかければかなり数は減ると思います。(多分100以下にはなってるんじゃないでしょうか)
まあさらにふるいにかけてもいいですし、残った数字を１つずつ調べてもいいと思います。

証明方法ですが、「その数字を、１とその数字自身以外では割り切れない」ことを示せばいいわけなんですが、数字が500以上と大きいので、全部調べるのは至難のわざです(できなくはないですが)で、約数とは何ぞや？ということを考えていくと、例えば12の約数は1,2,3,4,6,12なわけですが、これは
1*12=2*6=3*4=12となり、ある整数をa、aと同じかそれより大きい数字をbとして、a*b=12と表現できることになります。ということは大小関係を考えた時(bはaより小さくはない)aは６とはなり得ないことがわかります。(6*6=36で12を超えてしまう、a=2、b=6はOK)このように考えていくと、素数であることを示すには、
「２乗してその値を超えない値」まで調べればよいということがわかります。ちなみに32*32=1024なので、500以上1000以下の整数が素数であるかどうか調べるなら、その数字を２で割り、３で割り、４で割り、とずっと進めて、最大でも32までの中に割り切れるものがなければそれは素数であると言えることがわかります。

以上、参考になれば幸いです。

お礼

ご丁寧にありがとうございます。
最後の3行が完全には理解できなかったのですが、
その他は理解できたのでよく参考になりました。

ｐ、ｓ
これってエラトステネスとは少し違った新しい
考え方じゃないですか？？
私の勘違いかもしれないんですけど・・・