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

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

さて素数計算

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

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

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

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

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

ネーミングは「平方根」

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までの計算数は全数　⇒　素数は８９．８４％減りました。

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

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

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

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