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

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％減りました。