素数

質問

5000から10000の間の素数をひとつ求めなさい。

という問題なんですけどひとつひとつ見通しもなく調べてたら
大変な時間がかかってしまうと思うんですけど、なにか素数を求めるいい方法ありますか？

あとそれが素数だと確認できる方法はありますか？

だれか教えていただけたら助かります。

回答No.4

info22 · ベストアンサー

見通しは
偶数、3の倍数、5の倍数、7の倍数
http://www.manabu-oshieru.com/sugakukiso/warikirerukazu.html
などを除外してやることです。

そうすればすぐ見つかります。
5000,5002,5004,5006,5008, ... 偶数で除外
5001,5004,5007,5010, ... 3の倍数で除外

従ってこれらを除外して5003から調べていくだけで
素数がすぐ見つかります。
5003,5009,5011, ...
今は１つ求めるだけなので
5003が素数かを調べれば、素数だと分かります。

70=√4900<√(5003)<71=√5041なので
1～70までの全ての素数（2, 3, 5, 7, 11, 13, 17, 19, 23, 29. 31, 37, 41, 43, 47, 53, 59, 61, 67）で割り切れないこと確認してやればいいということです。

回答No.5

tsukita

問題の場合（問題の範囲5000～10000）であれば、
メルセンヌ素数の中にも該当するのもが存在します。
M_13=2^13-1=8191が今回の問題の答えの１つになります。

手計算しかダメであれば、これまでの回答者の方々が説明しているように「エラトステネスのふるい」を使うのが良いと思います。もし電卓等を使用してよいのであれば、"メルセンヌ数"と"リュカテスト"の話題もおもしろいですね！

参考URLはWikipediaのメルセンヌ数の項です。
http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E6%95%B0
リュカテスト（素数判定法）の部分で、S_0=4のところは、おそらくS_1の間違いですね。

参考URL：

http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E6%95%B0

回答No.3

Tacosan

まず, 自分でみつけるというなら #2 もいわれるように「エラトステネスのふるい」という方法が一番簡単かな. これだと, 得られた数は確実に素数となります.
また, 数字が突然降ってわいた場合でも, #1 で挙げられているように, 決定論的に, あるいは確率論的に与えられた数が素数であるかどうかを判定するアルゴリズムは存在します.
ただ, 10000 くらいだとたぶん「平方根までのすべての素数で割ってみる」のが早いんじゃないかなぁという気がします. 最悪でも 97 までの 25個で割ってみれば OK. もちろん 2 とか 5 で割ることは考えなくてもいいですけどね.
きっと「表を当たる」のは反則なんだろうなぁ. 語感からしても「求める」ってイメージじゃないし.

回答No.1

denden015

ヒント．
「エラトステネスのふるい」
を調べてみましょう．

回答No.2

noname#152554

http://wpedia.goo.ne.jp/wiki/%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A/?from=websearch

「素数判定」と言うモノが有ります。
ご参考までに。