mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Software (https://www.mersenneforum.org/forumdisplay.php?f=10)
-   -   Generating Small Primes (https://www.mersenneforum.org/showthread.php?t=3510)

wblipp 2005-01-05 05:16

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?

leifbk 2005-01-05 07:00

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.

Mystwalker 2005-01-05 13:29

[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...


All times are UTC. The time now is 23:45.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.