で、いろいろやってみた。
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/lounge/file/1035246186_14/hurui2.cpp
なんだかすっきりしたが、

>>903
に指摘されたような問題は解決されていない。

% time ./hurui2 1000000000 > primes
135.490u 6.520s 2:32.30 93.2% 0+0k 24+41io 0pf+0w

10億で2分半。18秒？ハハッ！