【素数】確率的素数生成【Python】

n番目の素数が与えられた時、n+1番目の素数を予測する。

アルゴリズムのアイデアは前回の記事と同様なので、それを貼り付けておく。

sky-time-math.hatenablog.jp

コード

パラメータの調整でどこまで成功確率が上がるかわからないが、ひとまず素数2,3,5を出発点として、確率的に100個素数を生成して、どれくらい正しい素数が含まれていて、次の素数を正しく計算できる確率を算出してみた。

確率的アルゴリズムのため、比較的うまくいった結果をとりあえず載せてみる。

github.com

gist6e61390f695c422cab264792f36581d4

このように約41％の確率で素数判定に成功しを、素数から次の素数を見つける確率は約40％である。最高で、49％付近までいったこともあるが、うまくいかないときは、35%程度である。

素数2~29を出発点として、確率的に素数を生成した場合の結果は次のように、いい時で50％付近まで改善された。元になる素数の情報が多いので当然の結果である。

gist5c4b2d564f917487dbb11a65163ed002