about prime number generation

John Gatrell gatrelljm at gmail.com
Wed Jun 1 12:54:21 CEST 2022


I took a look at the website for Atkin sieve
http://compoasso.free.fr/primelistweb/page/prime/liste_online_en.php
It does not give the segmented sieve a fair comparison.
The segmented sieve should use a bitset for odd numbers, not for all
integers.
I find that a fully optimised segmented sieve is twice as fast as Atkin for
small numbers.
For large numbers the segmented sieve wins due to Atkin's excessive memory
usage and cache misses.
On an old slow Athlon cpu I can get primes up to 2^35 in 2 minutes 30
seconds.
The only sieve I know of that is faster than segmented sieve is the one on
github hidden in primecount.c.
I would seriously stick with the segmented sieve.
On the other hand if you could invent a segmented version of Atkin, that
would change everything.
John Gatrell


More information about the gmp-discuss mailing list