下記の記事を読んで、10兆までの素数を現実的な時間で実際に生成する戦略を練ってみた。

- 10兆までの素数のリストを作ってみませんか？ (記者の眼：ITpro)
http://itpro.nikkeibp.co.jp/article/Watcher/20100519/348242/

とりあえず、ざくっと作った Perl スクリプト。
ものすごく時間はかかるけど（何ヵ月とか何年とか？）、とりあえず10兆までの素数が生成できる（はず）。

コード(gen-prime.pl):

#!/usr/bin/perl
use strict;
use warnings;
my $target = 10000000000000;
my $max_pn = sqrt($target);
my @pn;
for (my $n = 2; $n < $target; $n++) {
    for (my $i = 0; $i < @pn; $i++) {
        goto NOTPN if $n % $pn[$i] == 0;
        last if $n/$pn[$i] <= 2;
    }
    if ($n < $max_pn) {
        push @pn, $n;
    }
    print "$n\n";
  NOTPN:
}

プログラムに必要なメモリ容量についての考察。
10兆は10の13乗(10^13)。
ルートを取ると3162277.66...。
つまりプログラムは最大3162277までの素数を持てば良い。
実際の素数の数は約23万個。
23万個の素数をリストとして保持すれば良い。

実時間で終了させるには並列化が必要。
ということで、異なるマシン(CPU)で動かす前提のプログラム。

コード(gen-prime-p.pl):

#!/usr/bin/perl
use strict;
use warnings;
my $new_from = shift;
my $new_to = shift;
my $target = 10000000000000;
my $max_pn = sqrt($target);
my $flag;
my @pn;
for (my $n = 2; $n < $target; $n++) {
    for (my $i = 0; $i < @pn; $i++) {
        goto NOTPN if $n % $pn[$i] == 0;
        last if $n/$pn[$i] <= 2;
    }
    if ($n < $max_pn) {
        push @pn, $n;
    } elsif (not $flag) {
        $n = $new_from;
        $target = $new_to;
        $flag = 1;
    }
    print "$n\n";
  NOTPN:
}

ロジックは以下の通り：
(1) 3162277までの素数を得て数字リストとして保持する。
(2) その後はあらかじめ指定された3162277以降10兆までの分割領域に対して素数判明処理を行う。
(3) 素数と判明したらメモリに保持せずすぐに出力する。

実行例（例えば、それぞれ別マシンで動かす）:

./gen-prime-p.pl 3162277 1000000000
./gen-prime-p.pl 1000000001 2000000000
./gen-prime-p.pl 2000000001 3000000000
...

3162277（23万）の代わりに、分かりやすく 10^7 の値にしちゃってもいいかと。ざっくりと。
- Prime Counting Function -- from Wolfram MathWorld
http://mathworld.wolfram.com/PrimeCountingFunction.html

n (10^n)	素数の数
6	78498
7	664579

10兆までの全素数を単純にファイルに出力すると5Tバイトほどになるみたいなんだけど、素数そのものではなく差分を出力するようにすればだいぶ減らせる気がする。
どうせシーケンシャルにしかアクセスしないだろうから、ビット詰め詰めで良いしな。

素数判定アルゴリズムって、いろいろあるなあ→Wikipedia:素数判定。
前述のプログラム、確率的素数判定法でフィルタリングするともっと速くなりそう。深入りしすぎっぽいのでやらないけど。
（追記100530: 「Miller-Rabinは該当範囲について正確な判定が保証されてるアルゴリズムがある」ことを教えて頂きました。ありがとうございます。後日やってみます。 http://www.prefield.com/algorithm/math/isprime.html ）

ref.
- [を] Perlで素数判定と近隣素数の探索[2006-08-15-2]