about prime number generation

[Hans Åberg]

> On 1 Jun 2022, at 12:54, John Gatrell <gatrelljm at gmail.com> wrote:
> 
> 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.

There is a program using Atkin by Bernstein from 1999:
http://cr.yp.to/primegen.html

This link says there is a segmented version in section 5 of the original Atkin/Bernstein  paper. It is unclear if the program above has it.
https://stackoverflow.com/questions/10429747/segmented-sieve-of-atkin-possible

In my unoptimized program, timing Eratosthenes, there is a factor 5 between n = 10⁹ = 1E9 and m = 2³⁵ = 34.359738368E9 in addition to the factor m/n. So a segmented version seems essential.

I use C++ std::vector<bool>, which is a bitmap, slower, but 2³⁵ is just 4 GB then.