Go Back > Great Internet Mersenne Prime Search > Software

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

23×103 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's Avatar
May 2004
Oslo, Norway

12010 Posts

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's Avatar
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...
Mystwalker is offline   Reply With Quote

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 21:01.

Sun Nov 28 21:01:25 UTC 2021 up 128 days, 15:30, 0 users, load averages: 1.62, 1.39, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.