【素数判定】分解に基づく素数判定の劇的改良(99.58%)【Python】

前回の反省点

前回の記事では、判定成功率55％程度とあまりぱっとしなかった。

sky-time-math.hatenablog.jp

そこで、少し悩んだ結果、明らかに2,3,5,7などで割れるのは合成数だという情報を使っていなかったことに気づいた。また、プログラムのフローに問題があったので修正した。

修正版

github.com

gist388a80711e815a542ee7cb6bd9525809

1~1万までの自然数に対して試した結果、なんと判定成功率99.58%となった。素数だけの判定成功率は脅威の100%だった。なお、乱数による分割は書く自然数に対して、100回ずつ行っている。

自然数の素因数の種類数

追記

2,3,5,7の倍数をサンプルから除いた場合の素数判定成功率も調べた。

gist1610dbf28d8e1fe3b3016b3561d329d4

2,3,5,7の倍数をサンプルから除いた場合の判定成功率は約99%で、素数を正しく素数と判定できる確率は100%であった。