>>126　のソースコードの作者だけど、Delﾌｻｷﾞｺ さんのソース良さげな感じ。
そのうちアイディア取り入れさせて貰います。

>>371
エラトステネスの篩いにおいて、ある数Nが合成数かどうか知るためには
√Nまでの素数リストがあれば十分です。

逆に言えば2からMまでを篩った結果（小素数表）があれば、それを用いて
M+1からM^2までを篩うことができます（拡張素数表）。

そして、拡張素数表の部分は一度に篩う必要はないです。任意サイズに
分割することができます。

ただし、

1. 分割すると、各分割の先頭でoffsetを定めるための除算が必要になるので
　 分割しすぎると除算のコストが高くなる。

2. 分割が少なすぎると、一度に篩うべき領域が大きくなるので、キャッシュが有効に
　　働かず、メモリーアクセスのコストが高くなる。
　　最悪の場合、swapが頻発してHDにアクセスしてしまうかもしれない。

という条件を考えて適切な分割サイズを定める必要があります。
これはマシンの一次,二次キャッシュのサイズにも依存しますし、微妙なところです。
とりあえず256KBあたりが無難な線ですが、多分最適サイズは他にあります。

分割された各領域の先頭でoffsetを定めるところだけ64bit演算を導入すれば、
32bitマシンでもあまり代わったことをしないで32bitMAXより上を篩うことも可能です


# ……最近某所で、キャッシュを有効にするための凄まじい方法も聞きました。