Sieve of Atkin, by DJB claims "50847534 primes up to 1000000000 in just 8 seconds on a Pentium II-350": http://cr.yp.to/primegen.html Written in C, YMMV.