A 回答 (2件)
- 最新から表示
- 回答順に表示
No.2
- 回答日時:
素数は約数ととても近い関係にあることはわかりますね?
そこで、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
- 回答日時:
エラトステネスのふるいですか…
私もちょっとうろ覚えなんですが、結局何か整数の倍数になってるものは素数なわけないんだから、それを取り除いていけば残った数字は素数なんじゃね?ってやつですよね?
例えば500~1000というと501個の数字がありますが、その中で偶数は素数なわけない(2の倍数だから)251個しか考える必要はないですよね?
で、3の倍数も違う→5の倍数も違う→7の倍数も違う、ぐらいでふるいにかければかなり数は減ると思います。(多分100以下にはなってるんじゃないでしょうか)
まあさらにふるいにかけてもいいですし、残った数字を1つずつ調べてもいいと思います。
証明方法ですが、「その数字を、1とその数字自身以外では割り切れない」ことを示せばいいわけなんですが、数字が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*6=36で12を超えてしまう、a=2、b=6はOK)このように考えていくと、素数であることを示すには、
「2乗してその値を超えない値」まで調べればよいということがわかります。ちなみに32*32=1024なので、500以上1000以下の整数が素数であるかどうか調べるなら、その数字を2で割り、3で割り、4で割り、とずっと進めて、最大でも32までの中に割り切れるものがなければそれは素数であると言えることがわかります。
以上、参考になれば幸いです。
この回答へのお礼
お礼日時:2010/08/22 03:24
ご丁寧にありがとうございます。
最後の3行が完全には理解できなかったのですが、
その他は理解できたのでよく参考になりました。
p、s
これってエラトステネスとは少し違った新しい
考え方じゃないですか??
私の勘違いかもしれないんですけど・・・
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 大学数学 代数学の問題です。 もしわかる方がいらっしゃいましたらぜひ教えてください。 宜しくお願いし 1 2022/11/30 13:34
- その他(プログラミング・Web制作) pythonにおける単方向リストの実装について 4 2022/07/13 12:34
- 数学 x^p-1=(x-1)(x-ζ)(x-ζ^2)・・・(x-ζ^p-1)と複素数の中で因数分解できる理 1 2022/11/23 14:59
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- 数学 画素数の計算 中高レベルの計算で申し訳ないのですが、下記の問題が分かりません 比率が4:3のA4の横 3 2022/12/17 22:41
- Excel(エクセル) エクセルの数式で教えてください。 2 2023/04/13 10:55
- 数学 【 数A 自然数の積と素因数の個数 】 2 2023/03/02 23:58
- Excel(エクセル) エクセルの数式で教えてください。 2 2023/01/10 09:15
- 数学 nは正の整数であり、偶数。 n(n+1)(n+2)(n+3)は素因数が3つ。 nを求めよ。 という問 8 2022/09/26 18:15
- 化学 水分子について。 水は化学式でH2Oと表せますが、化学反応式になると 2H2+O2→2H2Oになりま 3 2023/02/15 15:38
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
インターネットでの数学の記号...
-
0.75乗の計算方法(電卓を使って)
-
4?4?4?4=10の?に+-×÷( ...
-
【至急】平方根の中の二乗につ...
-
無理関数の極限の問題でどの式...
-
三角形の一辺の長さを求めるには?
-
1から100までの
-
x と y の範囲
-
平方根の求め方
-
ルート9はなぜ-3ではないのです...
-
ルート8 × ルート12
-
√20a/3 が自然数と自然数となる...
-
昔のCMの歌詞
-
三平方の定理を学んで今後の生...
-
四分の三乗って?
-
こっちの画像では45度のときル...
-
数的推理の問題です。 この問題...
-
(√6-√2)^2のやり方を教えて...
-
2√10がなんで10何ですか? √100...
-
二次方程式x^2-2x+6+2√6=0を解...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
0.75乗の計算方法(電卓を使って)
-
【至急】平方根の中の二乗につ...
-
標準偏差
-
インターネットでの数学の記号...
-
4?4?4?4=10の?に+-×÷( ...
-
ルート9はなぜ-3ではないのです...
-
四分の三乗って?
-
√の中がマイナスになった時、i...
-
昔のCMの歌詞
-
高校課題数学の問題です。 √20a...
-
平方根の求め方
-
なんで 1/3=0.33333 なのに0.33...
-
2√10がなんで10何ですか? √100...
-
5の5/4乗とその他質問
-
こっちの画像では45度のときル...
-
某小説で、「登山は数学と似て...
-
数学の問題でルートとルートの...
-
ルートの中身は絶対、正 なのに...
-
(√2+√5)² この式を計算しな...
-
根号のない形に表す
おすすめ情報