【最大10000ポイント】当たる!!質問投稿キャンペーン!

 1000までの素数をすべて調べるには、どうすればいいのかを教えてください。さらに、300番目の素数を知るにはどうすればいいでしょうか。

このQ&Aに関連する最新のQ&A

素数」に関するQ&A: 素数は無限

A 回答 (3件)

nまでの素数を全て調べると言うときはエラストテネスの篩いと言う方法が便利です。


まず、1~1000の数字を全部書き出します
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20

981 982 983 984 985 986 987 988 989 990
991 992 993 994 995 996 997 998 999 1000
1は素数ではないので消します。
2以外の偶数を全部消します。(最初から奇数だけ書いてもよい
3以外の3の倍数を消していきます。
次の数(4は2の倍数を消したときに消えてるので5)の倍数を全て消します。
これを繰り返し√1000=31の倍数まで全部消せば残った数字は全て素数です。
nまでの合成数(素数で無いもの)は全て√nまでの素数の積で表すことができます。

31までの素数は
2,3,5,7,11,13,17,19,23,29,31
です。
    • good
    • 4

記事抜粋ですが。

。。
「素数を求める公式は現在のところ発見されていません。
しかし、地道な作業で素数を一つずつ洗い出していくことは可能です。」

だそうです。
もし、何らかの試験などであれば代表的なものしか出ませんので、予め探すか解くしかないですね。

またはそういったのを考える、プログラミングするなら以下のURLを参考にしてみてはどうでしょうか?
http://www.zexv.com/sosuu/
地道ながらも方法が載ってます。

参考URL:http://www.zexv.com/sosuu/
    • good
    • 2

こんなページもありますが。



参考URL:http://www.zexv.com/sosuu/table.htm
    • good
    • 1

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q素数かどうかを知るには(手順)

ある数、とくに何桁もの数が素数かどうかを知るにはどんな手順がありますか?

私は(1)その数が10の倍数かどうか(2)2の倍数かどうか(3)9の倍数かどうか
しかわかりません。
(3)は、各桁の番号を足してそれが9の倍数なら9で割り切れるということです。

他の有効な手順があれば教えてください。

Aベストアンサー

一応素数を求める(かどうか判断する)式?は存在するそうです。何かの本で読みました。ただ例えば1000までの素数を書き出すのに自分の手を動かせば数時間もあればできるでしょう。しかしこの式を使うとコンピュータでやっても何日もかかるそうです。つまり式は存在するが実用的ではないのです。
でご質問の答えですが「エラトステレスの篩」を利用するのが適当ではないでしょうか?これは『ある数nが素数かどうか判断するとき√n以下の素数でnを割ったとき割り切れるものがなければそのnは素数である。』と判断できる方法です。

例えば953が素数かどうかを判断するなら√953=30.087…ですから
2,3,5,7,11,13,17,19,23,29の10個の数で割ってやるだけで判断できます。

Q素数の見分け方

いっけん素数にしか見えないような数を、素数ではないとすばやく判断する方法ってあるのでしょうか?

たとえば、841という数は、2でも3でも4でも・・・・・・割れず、順順に判断していっても、なかなか割り切れません。結局、根拠なく素数だと判断してしまいます。

ですが、実際は 841=29×29 なので、素数ではありません。

まともに考えていては、時間が足りないと思うのですが・・・何かうまい方法があるのでしょか?今日も、模試でこの問題が出て、だまされました(><)

数学に詳しい方、ご教授ください。

Aベストアンサー

一応「決定論的な多項式時間素数判定アルゴリズム」は存在します. 与えられた n (log n ビットで表してます) が素数かどうかを, (log n)^8 くらいの計算時間で判定するというものだったような....
まあ n が小さければ √n までの数で割ってみるのが簡単かと.


人気Q&Aランキング