【Python】素数判定の計算量を減らしていく【数学】

【Python】素数判定の計算量を減らしていく【数学】

はじめに

コジマです。

Pythonと素数を使って遊びました。

10〜10000の素数判定を行い、その実行結果と実行時間を表示します。

方針

1:定義に則る

一番ベタなやり方かと思います。
素数nは1とn以外の約数を持たないという定義を利用して
2〜n-1まで約数を持たないか地道に判定していきます。

2:1の位を見る

2の倍数は1の位が偶数
5の倍数は1の位が5or0
という性質を利用して素数でないことを判定します。
1の位が0,2,4,5,6,8の数字は素数でないことがわかります。

10で割った余りにだけ出せば良いので、該当する数字は計算が1回で済みます。

3:各桁の和をとる

3の倍数を判定します。
map関数を使用して桁ごとのリストを作成します。
sum関数でリストの総和を出せるので、それを3で割った余りを出します。

リストを作成する処理がありますが、その他の計算量は減ります。

4:n/2まで確認すれば十分

証明はしませんが、約数のi番目に大きい約数と1番目に小さい約数かけたらnになるので
半分以上の数ってチェックするする必要はないです。

5:奇数だけ見れば十分

偶数で割り切れるということは2で割り切れるので、それも見る必要ないですね。
3から1つ飛ばしに変えてみます。

6:エラストテネスのふるい

エラストテネスのふるいというの素数判定法としてあります。

√n以下の素数で割り切れなければnは素数という性質です。
ここでは証明しないですが、√n以上の2つの素数かけたらnより大きい数になるので
直感的にはそりゃそうだって感じです。

ここでは、√n以下の奇数で調べていきます。
√n以下の素数を作って律儀にやったら逆に遅くなったからおまけとして上げておきます!w

実装

1桁の素数はガン無視して、2桁以上の素数(10〜50000)について
素数判定していくプログラムを作りました。

実行結果の見た目の都合上
printで肝心の素数判定結果はコメントアウトしてます。

結果

パターン 時間
パターン1:地道に 21.0839(s)
パターン2:2の倍数と5の倍数 11.9452(s)
パターン3:3の倍数 11.5401(s)
パターン4:上限をn/2 5.7619(s)
パターン5:偶数を無視 2.8700(s)
パターン6:上限を√n 0.1017(s)

3の倍数判定はそんなに必要なかったですね。。。

競プロ的実装が加わればもっと速くできるのかもしれませんが、
数学的アプローチだけでここまでパフォーマンスが良くなりました。
21秒が0.1秒になるんですね。

さいごに

素数判定を行うプログラムを数学的アプローチでパフォーマンス改善してみました。

フェルマーの小定理も使おうかと思ったんですが、
フェルマーの小定理は必要十分な定理ではないため使用するのをやめました。
別で記事を書こうかななんて思います。

また、gistに上げたソースはgithubにも上げています。
https://github.com/kojimanotech/myDeriverables/blob/master/CheckPrime.ipynb

この記事を面白いまたは役に立ったと思ってくれた方は是非私のTwitter(@kojimanotech)を
フォローしてくれたらうれしいです!

以上、コジマでした。


Pythonカテゴリの最新記事