【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で肝心の素数判定結果はコメントアウトしてます。

結果

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

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

さいごに

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

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

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

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

もっと学びたい人はこちら

Python、機械学習をもっと学びたいという人のためにおすすめのUdemy講座を紹介いたします！

Pythonの基本文法を押さえたい方はこちらの動画がおすすめです。
エンジニアになりたいと思って駆け出した方がPythonを選んだときはこの講座から始めるとよいと思います。
Python 3 エンジニア認定基礎試験の対策にもなります。
はじめてのPython 少しずつ丁寧に学ぶプログラミング言語Python3のエッセンス

プログラムの基礎が分かる方で機械学習に興味がある方はこちらがおすすめです。
SIGNATEという日本版Kaggleのサービスを実際に使用してハンズオン形式でデータ分析・機械学習を学ぶことができます。
もちろんこの動画だけで特級のデータサイエンティストになれるわけではないですが、機械学習の門を叩くにはとても良い講座だと思います。
【ゼロから始めるデータ分析】 ビジネスケースで学ぶPythonデータサイエンス入門

Pythonのライブラリで必ず押さえておきたいのがNumpy, Pandas, Matplotlibの３つ。
この3つを網羅的に学ぶことができる講座です。
英語の講座ですが、わかりやすい英語ですし、ソースコードメインで解説しているので
ソースコードを一緒に手を動かしながら学べば十分理解することができます。
機械学習を使わない人にもおすすめの講座です。
2021 NumPy, Pandas and Matplotlib A-Z™: for Machine Learning

気になった人はぜひ見てみてくださいね！

以上、コジマでした。