10兆までの素数リスト - 雷雲の変奏曲プログラミングコンテストチャレンジブックを読んでいたら、素数リストの作り方が出てきた。 そういえば、１０兆までの素数リストを作ってみる、なんて記事があったな。 これだ http://itpro.nikkeibp.co.jp/article/Watcher/20100519/348242/?ST=develop 読み返しているうちに、ついつい挑戦してみる気になってしまった。 色々試して意外だったのが、10億までの素数をリストアップした場合でも「試し割り」より「エラトステネスの篩」の方が100倍以上も高速だったことだ。リストが大きくなればその差はますます開いていく。 メモリ上の広い範囲をまんべんなくアクセスするエラトステネスの篩は、実際には効率が悪いのではないかと思ったりしたのだが、見当が外れてしまった。 考察してみるに 試し割りは意外と無駄が多い。まず素数の密度だがn/log(n)に従うらし
