【Python】確率的素数生成プログラム【改良版】
バグがありました
素数が見つからないときは、取り合えず２を足す作戦に変更
ついでに、sympy.isprime()で素数判定する作戦に変更。プログラムは以下においてあります。
進捗バー表示は以下のサイトを参考にした。
素数2,3,5だけから始めて、200個の素数を生成するテスト。prodの積の最大値は５、その各場合につき、乱数は1つの素数につき、100パターン取っている。
gist02db7518e164c1786a5adcb24fbc4f05
ある素数の次の素数を見つける確率99.01%。素数を見つける確率99.51%。
素数2,3,5だけから始めて、1万個の素数を生成するテスト。prodの積の最大値は10、その各場合につき、乱数は1つの素数につき、100パターン取っている。
gist6a1bd58014cb3df8b65e40ad4578de35
ある素数の次の素数を見つける確率99.02%。素数を見つける確率99.99%。しかし、28分もかかってしまった。
次にすべきこと
上記のプログラムでは素数生成時に、それまでに生成した素数全てを用いている。それを減らして、例えば100個の素数から生成し直した場合どうなるかなど調べた。1万個の素数を生成するテスト。prodの積の最大値は10、その各場合につき、乱数は1つの素数につき、100パターン取っている。この計算には、1分50秒で済んだ。
gist40988ad27e18a3c3148b3d71601ab7f0
ある素数の次の素数を見つける確率98.97%。素数を見つける確率99.99%とかなりの好成績を収めてくれた。
まとめ
確率的素数生成プログラムとしては、ある程度の水準のものができたように思う。これ以上改良するには、最初に用意する素数を増やすなどの手を打つ必要があるだろう。どれくらいの大きさの素数に対して、いくつ素数を事前に用意すればよいか、素数を選ぶ重みづけなど、いくつか課題は残っている。
