Generating Small Primes
 

What's the fastest way to generate small primes? Crandall & Pomerance give a "Fancy Erotosthenes Sieve" in Algorithm 3.2.2 that is O(N / ln ln N). At about the same time Atkin and Bernstein published their sieve with binary quadratic forms that has the same asymptotic density. Has experience yet shown one to be better in practice?

Calculating these and saving the results in a compressed bit map must be a common function. Has somebody optimized this and made source code available, or does everybody recreate this for themselves?

Don't know if you've seen [URL=http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm]"Fun with Prime Numbers"[/URL] or even find it useful ...

regards, Leif.

[URL=http://cr.yp.to/primegen.html]Primegen[/URL] (comes as source) uses the Sieve of Atkin and seems to do fine - I don't know about the Big O, though...