最近どこかのブログで
素数を求めるコートが載っていました。

今回はいろんなコードで
素数を求めてみます。

コードによる計算回数の違いや
速度なんかが気になってしまいました。

解説動画はこちら



さて素数ですが知らない人は
ほとんどいないと思いますが

そんな素数を求めるコードを考えてみましょう。

まずは2からその素数まで愚直に割っていきます。
素数の候補は6桁の素数である999983です

これが素数かどうかを判定していきます。


1.愚直に割って求めるプログラム

def isPrime1(num):
    count = 0
    if num<2:
        return False
    for k in range(2,num):
        count+=1
        if num % k==0:
            return False
    #print(count)
    return True

%timeit -n1 isPrime1(999983)

Jupyter Notebookでは

%timeit -n回数 コード

と書いて実行すると
そのコードを何回か実行して
その計算時間を測ってくれます。

この場合の計算回数は999981回でした。
その素数の数と同じような計算回数ですね。
非常に時間がかかっています。

つぎは計算回数を減らしてみましょう。
割るのをその候補のルートを取った
数までにしてみます。

2.計算回数を減らしてみる

import math

def isPrime2(num):
    count = 0
    if num<2:
        return False
    for k in range(2, int(math.sqrt(num)) + 1):
        count+=1
        if num % k == 0:
            return False
    #print(count)
    return True

%timeit -n1 isPrime2(999983)

これで計算回数も大幅に減り
998回まで減りました。

実行速度の方もmsからμsまで減っています。
大幅な速度アップですね。

それでも割るのは無駄が多いです
2で割れたら素数では無いので
改めて偶数で割る必要は無いですよね。

偶数を抜いて割るのを奇数だけにしてみます。

3.割るのは奇数のみにしてみる

import math

def isPrime3(num):
    count = 0
    if num==2:
        return True
    if num<2 or num%2==0:
        return False
    for k in range(3, int(math.sqrt(num)) + 1,2):
        count+=1
        if num % k == 0:
            return False
    #print(count)
    return True

%timeit -n1 isPrime3(999983)

さて奇数で割るだけにしただけでも
かなり早くなりましたが、それでも
まだまだ無駄があります。

5で割り切れるなら改めて
15で割る必要は無いですよね。

割るのを奇数から
素数だけにしてみましょう。


4.あらかじめ素数を用意しておき
割るのを素数だけにする

def isPrime3_2(num):
    if num==2:
        return True
    if num<2 or num%2==0:
        return False
    for k in range(3, int(math.sqrt(num)) + 1,2):
        if num % k == 0:
            return False
    return True

prime_numbers = [i for i in range(2,999983+1) if isPrime3_2(i)]

あらかじめ沢山の素数を用意しておきます。
改めて素数だけで割ってみます。

def isPrime4(num):
    count = 0
    if num<2:
        return False
    elif num==2:
        return True

    m = math.floor(math.sqrt(num))
    for p in prime_numbers:
        count+=1
        if num % p == 0:
            return False
        if p > m:
            # 素数がnの平方根を超えたら終了
            break
    #print(count)
    return True

%timeit -n1 isPrime4(999983)

12.2 µs ± 1.35 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

計算回数も169回と大幅削減ですが
最初に素数を沢山用意しておくのがネックです

素数計算を沢山やる必要があるなら
プログラムとしては許せますが
桁が多くなったりすると対応しきれません。

そんな訳で最後の手です。

5. from sympy import isprimeを使ってみる

sympy はPythonで
記号計算を行うためのライブラリです。

その中には素数を求めるメソッドが
あらかじめ用意されています。

isprime

これを使ってみましょう。

from sympy import isprime

%timeit -n1 isprime(999983)

さて、計算回数は分かりませんが
実行時間は先ほどの素数をあらかじめ用意したものと
さほど変わりません。

であれば、Pythonでは
わざわざ素数を求めるような
関数とか作る必要が無いですねーーー

githubに関数のソースがあるようなので
みてみると良いかもしれないですね。
sympyのソース


ということでまとめです。
こういった素数を求める関数を作るような事を
車輪の再発明と言います。

勉強のためであれば
良いとは思いますが業務で行う場合は
時間の無駄になる事がほとんどです。

こういった課題というのは時折
コードを書かせる試験などで
用いられるようですが

入社後はあまり役には
立たないかもしれませんね。

システム開発の際は
車輪の再発明にならないように
色々と調査をしておくと
無駄が少なく工数を節約できる
こともあるので日々の情報収集は
大事ですね。

今回はこれまでです
それでは。

タグ ：

#Python

#プログラミング

#素数

#アルゴリズム