View Single Post
Old 2005-01-05, 05:16   #1
wblipp's Avatar
May 2003
New Haven

3·7·113 Posts
Default 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?
wblipp is offline   Reply With Quote