素数には不思議な魅力があるらしく
度々、素数を作らされる。最新の値を発見すると賞金もでるらしい。
昨日の素数の問題を解いていて巨大な素数つくれるのではないかと作ってみました。
1万まではあっという間なのですが、1万から1億までの計算だといつ終わるのか
サッパリわからないので100000番目ごとに値と計算時間を表示させています。
1億から1京だと素数の計算テーブル数も575万程度
計算をしている間にどこまで世界に迫っているか調べてみると...
徳川吉宗が生存していた頃、1750年なら世界一かもしれません。
現在の最大と認識されている素数は
24,862,048桁の数値M51という星雲のような名前がついています。
8桁 vs 24,862,048桁 世界はとんでもないところまで到達していました。
少し調べていると偉大な先人達のブログに
エラトステネスの篩という高速化のアルゴリズムの記述があったので、実装してみました。
速度が15倍ぐらい速くなったのでさあ、19世紀に到達だ！
と思ったのですが、次へ進むとcolaboratoryがメモリーオーバー(追加もできるらしい)
それならメモリ消費の少ないnumpy利用に変更
それでもだめなので、ローカルでやろうかと思ったのですが...
自宅のパソコンのスペック、速度、メモリともにネットワーク上のcolaboratory端末の方が上でした。
ソースのテキスト版
import time
import numpy as np
#巨大な素数生成
def primeKusi(sosuTable,s,e):
plusTable=np.array([True]*(e+1))
c=len(sosuTable)
for i in sosuTable:
for j in range(i*2,e+1,i):
plusTable[j]=False
return np.array([n for n in range(s,e+1) if plusTable[n]])
st=time.time()
base=np.array([2,3,5,7])
#100までの素数
base=np.hstack((base,primeKusi(base,10,100)))
print(base[-1])
#10000までの素数
base=np.hstack((base,primeKusi(base,100,10000)))
print(base[-1])
#100000000までの素数
base=np.hstack((base,primeKusi(base,10000,100000000)))
print(base[-1],len(base)+1,"番目")
print(round(time.time()-st,2),"s")
#メモリーエラー
#base=np.hstack((base,primeKusi(base,100000000,100000000000000000)))
#print(base[-1])
