素数をみつける方法を教えて下さい

質問

早速ですが、素数を少しでも楽に見つけ出す方法が知りたいです。
私はエラトステネスの篩「自然数NがNの平乗根を超えない最大の整数以下の全ての素数で割り切れなければ、Nは素数である」
は知っています。他にも素数を少しでも楽に見つけ出す方法を教えてください。

回答No.4

proto · ベストアンサー

見つける方法というよりは、ある数Nが素数かどうか判定する方法ですが、
Nが非常に大きくなると√N以下の整数も多くなり、順番に割っていくことが困難になります。

そこで具体的にNの因数を見つけることなく、確率的に素数を判定する方法があります。
(仮に合成数であることがわかっても因数分解する役には立たない)

フェルマーの素数判定法
http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86
ラビン-ミラー素数判定法
http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%93%E3%83%B3-%E3%83%9F%E3%83%A9%E3%83%BC%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
等を調べてみてください。

回答No.3

SortaNerd

Wikipediaにいろいろ載っています。
http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A
が、私には理解できません…。

回答No.2

sugakusya

#1の回答を見て思いついた素人考えですけど
２^n － 2m+1　（mは0と自然数）
の集合から探す方法はどうですか？
（メルセンヌ数中の出現率とどちらが高いか知りませんけど。
カンですけど数字が大きくなるとメルセンヌ数のほうが出現率が高いかも。）

例えば
n=2 →　4-1 = 3
n=3 →　8-1 = 7 , 8-3 = 5
n=4 →　16-1=15 ,16-3 =13,16-5=11

2^nのステップでは 2^(n-1) ～ 2^n の間だけ探せばいいですね。
あとwikipediaにも素数生成式というものが載ってましたよ。

（これぐらいの意見で書いたら失礼か？）

回答No.1

Ganymede

メルセンヌ数の中から探す。