素数ファイル - ita’s diaryhttp://itpro.nikkeibp.co.jp/article/Watcher/20100519/348242/ 10^13 までの素数をファイルに格納する問題。 5Tバイトか！すごいね。なんとかもっと最適化できないか考えたけど、元記事もかなり頑張ってる模様。 10^13あたりの素数分布を見てみると、だいたい300間隔くらいになってる。なので値自体じゃなくて前の素数との差を記録するようにすれば１つあたり２バイトあればいい。これで計算すると5Tバイトになる。 600Gバイト もっと頑張るとすれば、素数は奇数なので間隔は常に偶数。したがって間隔/2を記録すればいい。こうするとほとんどが256以下になって1バイトで記録できる。 という訳で以下のようなフォーマットで、ある数以上ある数以下の素数を保存するファイルを考える。まず素数256個くらいをひと塊にしてブロックに分割する。8bit でO
