素数の調べ方

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

No.3 ベストアンサー 回答者： ryuta_mo 回答日時： 2004/12/08 00:17

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

まず、１～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
１は素数ではないので消します。
２以外の偶数を全部消します。（最初から奇数だけ書いてもよい
３以外の３の倍数を消していきます。
次の数（４は２の倍数を消したときに消えてるので５）の倍数を全て消します。
これを繰り返し√１０００＝３１の倍数まで全部消せば残った数字は全て素数です。
nまでの合成数（素数で無いもの）は全て√nまでの素数の積で表すことができます。

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

No.2 回答者： CupNaka 回答日時： 2004/12/07 19:23

記事抜粋ですが。

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

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

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

参考URL：http://www.zexv.com/sosuu/

No.1 回答者： 2mama 回答日時： 2004/12/07 19:22

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

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