mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2005-01-05, 05:16   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·5·59 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
Old 2005-01-05, 07:00   #2
leifbk
 
leifbk's Avatar
 
May 2004
Oslo, Norway

23×3×5 Posts
Default

Don't know if you've seen "Fun with Prime Numbers" or even find it useful ...

regards, Leif.
leifbk is offline   Reply With Quote
Old 2005-01-05, 13:29   #3
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3×277 Posts
Default

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

Thread Tools


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

All times are UTC. The time now is 04:28.

Wed Dec 2 04:28:33 UTC 2020 up 83 days, 1:39, 1 user, load averages: 2.32, 2.43, 2.36

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.