【素数】確率的素数生成【Python】
n番目の素数が与えられた時、n+1番目の素数を予測する。
アルゴリズムのアイデアは前回の記事と同様なので、それを貼り付けておく。
コード
パラメータの調整でどこまで成功確率が上がるかわからないが、ひとまず素数2,3,5を出発点として、確率的に100個素数を生成して、どれくらい正しい素数が含まれていて、次の素数を正しく計算できる確率を算出してみた。
確率的アルゴリズムのため、比較的うまくいった結果をとりあえず載せてみる。
gist6e61390f695c422cab264792f36581d4
このように約41%の確率で素数判定に成功しを、素数から次の素数を見つける確率は約40%である。最高で、49%付近までいったこともあるが、うまくいかないときは、35%程度である。
素数2~29を出発点として、確率的に素数を生成した場合の結果は次のように、いい時で50%付近まで改善された。元になる素数の情報が多いので当然の結果である。
gist5c4b2d564f917487dbb11a65163ed002