普通にエラトステネスの篩を実装した場合。
バグはありそうな気がする。
http://codepad.org/UPzb5pV5

出力結果の1000001番目の素数が15485867であることを照合済み。
http://www.bigprimes.net/archive/prime/10001/


ところで、こういうネット上のアーカイブからとってくるというアイデアをすっかり忘れてたわ。
巨大なテーブルは既にネット上にあるさね。