Generating Small Primes

wblipp · 2005-01-05, 05:16

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 "Fun with Prime Numbers" or even find it useful ...

regards, Leif.

Mystwalker · 2005-01-05, 13:29

Primegen (comes as source) uses the Sieve of Atkin and seems to do fine - I don't know about the Big O, though...

2005-01-05, 05:16	#1
wblipp "William" May 2003 Near Grandkid 5³×19 Posts	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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve	mickfrancis	Factoring	2	2016-05-06 08:13
Small primes	kar_bon	Riesel Prime Data Collecting (k*2^n-1)	3	2013-05-11 04:56
Generating Random Primes	davar55	Math	14	2011-02-20 16:06
Small Primes	Housemouse	Math	2	2008-06-04 05:23
Small Primes for Octoproths <= 155	ValerieVonck	Octoproth Search	100	2007-02-16 23:43

2005-01-05, 07:00	#2
leifbk May 2004 Oslo, Norway 1111000₂ Posts	Don't know if you've seen "Fun with Prime Numbers" or even find it useful ... regards, Leif.

2005-01-05, 13:29	#3
Mystwalker Jul 2004 Potsdam, Germany 3·277 Posts	Primegen (comes as source) uses the Sieve of Atkin and seems to do fine - I don't know about the Big O, though...