• ベストアンサー

素数の調べ方

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

質問者が選んだベストアンサー

  • ベストアンサー
  • ryuta_mo
  • ベストアンサー率30% (109/354)
回答No.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 です。

その他の回答 (2)

  • CupNaka
  • ベストアンサー率22% (13/57)
回答No.2

記事抜粋ですが。。。 「素数を求める公式は現在のところ発見されていません。 しかし、地道な作業で素数を一つずつ洗い出していくことは可能です。」 だそうです。 もし、何らかの試験などであれば代表的なものしか出ませんので、予め探すか解くしかないですね。 またはそういったのを考える、プログラミングするなら以下のURLを参考にしてみてはどうでしょうか? http://www.zexv.com/sosuu/ 地道ながらも方法が載ってます。

参考URL:
http://www.zexv.com/sosuu/
  • 2mama
  • ベストアンサー率15% (52/327)
回答No.1

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

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

関連するQ&A