10兆までの素数のリストを作ってみませんか？

日経ソフトウェアの記事です。

2010年とちょっと古いのだが、興味があったので私の過去記事も交えてみる。


10^13=10兆までの素数をファイル化することを考える。

先の記事にも、いくつかのボトルネックとなるところが書かれている。


10兆という値は、64ビット正整数型でなければ、表現出来ないということ。

16ビット正整数型では、
　0000hからffffhまで表現でき、0から6万5535まで
32ビット正整数型では、
　00000000hからffffffffhまで表現でき、0から42億9496万7295まで
64ビット正整数型では、
　0000000000000000hからffffffffffffffffhまで表現でき、
　0から1844京6744兆0737億0955万1615まで
と十分ではある。


ファイルにどのように保存するのか。

数値をそのまま文字列としてテキスト形式で保存したとすると、

範囲
素数の個数
ファイルサイズ
10^1=1048byte
10^2=1002571byte
10^3=1000168643byte
10^4=1万12295.81KB
10^5=10万959254.8KB
10^6=100万78498526KB
10^7=1000万6645794.98MB
10^8=1億576145548.7MB
10^9=10億50847534479MB
10^10=100億4550525114.61GB
10^11=1000億411805481345.5GB
10^12=1兆37607912018451GB
10^13=10兆3460655368394.37TB

となる。

最近ではテラバイトサイズのHDDも珍しくはないが、まだまだ現実的ではない。

もし、32ビット=4バイトの固定長のバイナリデータとして保存したとすると、

346065536839*4/1024^4≒1.26TB

となる。


さて、私も過去に素数のファイル化記事を書いている。

この方法で格納したとすると、

10^13/30/1024^3≒310GB

と、かなり現実味を帯びてくる。

このデータは圧縮されていませんので、圧縮すればまだダウンサイズ出来るかもしれません。



あとはどんなアルゴリズムで素数を見つけていくかということになる。



さて、こんな素数絡みの記事を書きたかったのは、

素数表150000個/暗黒通信団
￥375
Amazon.co.jp

15万個の素数表が375円という価格で販売されているという事実である。

因みに、15万番目の素数は2015177である。


他にも、

円周率1000000桁表/暗黒通信団
￥330
Amazon.co.jp

e―自然対数の底100万桁表/暗黒通信団
￥285
Amazon.co.jp

円周率や自然対数の底を100万桁です。


素数を15万個を隙間を1桁開けて並べると、960484桁となるので、円周率や自然対数の底と同等の冊子と考えてよいだろう。


もし、アメブロの1記事4万文字でやるとしたら、どれくらいまでの素数を書けるかな。

16進ダンプでやってみるかな。