素数チェッカー その３ もっと高速化

 素数を探求しているとはやし君は理系だね～と言われますが、完全な文系です！

さて素数計算

その１では素数かどうかを確認するターゲット数をそれ以下のすべての数で割っていました。「全数」とネーミング

その２では素数意義で割る必要がないとひらめき、ターゲット数をそれ以下のすべて素数で割りました。「素数」とネーミング

そして夜に考えていると、ターゲット数が１００として２で割ると５０

つまり１００の場合５１以上で割ることは無意味と気が付きました。

これを深く考えていくとターゲット数の平方根以上の数での割り算は無意味となります。

ネーミングは「平方根」

import time
print('素数チェッカー')
max=input('最大数')
start_time=time.time()
c=0
c1=0
s=[]
for i in range(1,int(max)+1):
    if i>2 and i%2==0:
        continue
    else:
        f=True
        sq=pow(i,0.5)
    for j in s[1:]:
        if sq<j:
            break
        c1+=1
        if i%j==0:
            f=False
            break
    if f:
        s.append(i)
        c+=1
print('Finished! 素数: '+str(c)+' 個 計算数: '+str(c1)+' 個 処理時間: '+str(float(time.time()-start_time))+'秒')
print(s)

平方根はpow( x,0.5)を使っています。

昨日とは違うPC（NOTE）で測定しています。

全数、素数も計測しなおしました。

計算数は変換し処理時間はかなり長くなっています

100,000までの計算数は全数　⇒　素数は８９．８４％減りました。

さらに、全数　⇒　平方根は９９．８５％減です。

素数　⇒　平方根は９８．５％減

処理時間は２２２秒　⇒　４秒　です。

東京から北海道まで２２２分かかっていたのが４分になったかんじです。

素数チェッカー その２ 高速化

Pythonの計算処理を早めるために少し考えました。

ターゲット数nを2,3,4,5,6と割っていき割り切れた時に終了

最後まで割り切れないときは素数リストに追加をしていましたが

２で割り切れる場合　偶数で割れるかどうかを計算する必要はありません。

同様に考えるとnを素数で割っていき割り切れない数は素数です。

import time
print('素数チェッカー')
max=input('最大数')
start_time=time.time()
c=0
c1=0
s=[]
for i in range(1,int(max)+1):
    if i>2 and i%2==0:
        continue
    else:
        f=True
    for j in s[1:]:
        c1+=1
        if i%j==0:
            f=False
            break
    if f:
        s.append(i)
        c+=1
print('Finished! 素数: '+str(c)+' 個 計算数: '+str(c1)+' 個 処理時間: '+str(float(time.time()-start_time))+'秒')
print(s)

わる数　j　を素数のリストにしました。
これで計算回数が激減し処理時間が短くなるはずです。

結果）

高速化はたのしい！

全数で割るパターンと素数だけで割るパターンの比較です。素数は同じ結果が出ました。

100､000まで計算をすると計算数は89％減りました。処理時間は90％減りました。

素数チェッカー

 最近　投資のことを書いていないとお叱りをいただきそうですが、

今日は素数を探してみます。

素数は１とその数以外で割り切れない数です

（中略）

Pythonです

import time

print('素数チェッカー')

max=input('最大数')

start_time=time.time()

c=0

c1=0

s=[]

for i in range(1,int(max)+1):

    f=True

    for j in range(2,i):

        c1+=1

        if i%j==0:

            f=False

            break

    if f:

        s.append(i)

        c+=1

print('Finished! 素数: '+str(c)+' 個 計算数: '+str(c1)+' 個 処理時間: '+str(float(time.time()-start_time))+'秒')

print(s)

最大数に入力した数までを２，３，４，・・・と割っていきます。

割り切れた場合終了、最後まで割り切れなかったときはリストに追加します。

10万まで計算すると4.5億回の割り算をしています。

ちなみに人類最大の素数は「2^89589933－1」です。 2486万2048桁とのことです

参照）同志社