めっちゃ素直にふるいを実装。
% time ./era 10000000 78497
prime[78497] is 999983
3.560u 0.390s 0:04.16 94.9% 0+0k 0+0io 0pf+0w
G４450Mhz でこのくらい。
「./era」がバイナリ。
最初の引数が、ふるいの大きさ。
次の引数で、いくつめの素数を表示するかを指定( チェック用 )

アイデアがあるので、これから改造。