I've had good luck with Stephan Brumme's block-wise sieve[1], also based on the Sieve of Eratosthenes. It's best when calculating several blocks in parallel, of course. But it's still pretty fast even when used sequentially. [1]: http://create.stephan-brumme.com/eratosthenes/