about prime number generation

[Hans Åberg]

> On 4 Jun 2022, at 11:39, Marco Bodrato <bodrato at mail.dm.unipi.it> wrote:
> 
> Ciao,
> 
> Il 2022-06-01 22:18 Hans Åberg ha scritto:
>>> On 1 Jun 2022, at 12:54, John Gatrell <gatrelljm at gmail.com> wrote:
>>> 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.
> 
> The program by Bernstein is old, but it still compiles and works after more than 20 years. It was (and it is) a very well written program!
> 
> I've not found a licence for that code, and I didn't read the sources, but I'm sure it is able to sieve ranges of numbers.
> 
> On a slow computer, it takes 4 seconds to list the 268 primes between 10^15-10^4 and 10^15.
> 
> ~/src/primegen-0.97$ time ./primes 999999999990000 1000000000000000|wc
>    268     268    4288
> 
> real	0m4,186s
> user	0m4,126s
> sys	0m0,026s

On a MBP 2.4 GHz, I get
primegen-0.97 % time ./primes 999999999990000 1000000000000000|wc
     268     268    4288
0.81s user 0.01s system 99% cpu 0.828 total

By contrast, time ./primes 1 1000000000000000|wc does not seem worth waiting for.

> For sure, it did not sieve all the primes up to 10^15;

So it seems.

> the very fast primecount program (by Kim Walisch) needs more time to simply count them all :-)
> ~/src/primegen-0.97$ time primecount -t1 1000000000000000
> 29844570422669
> 
> real	0m17,905s
> user	0m17,471s
> sys	0m0,054s
> 
> 
> On the other side, I believe also that GMP will not try to compete with primecount in speed. It is based on extremely specialized libraries.

The WP page Prime-counting function, sec. Inequalities [1], gives upper and lower bounds for the 𝑛-th prime 𝑝(𝑛), with the gap 0.1𝑛, which is large for 𝑛 = 10¹². So perhaps one can use the formulas for 𝜋(𝑘) to successively half it down, and then use a sieve for a smaller range.

1. https://en.wikipedia.org/wiki/Prime-counting_function


I compared timing of bitmaps std::vector<bool> with byte-based integral types std::vector<int8_t> etc.: Interestingly, for Eratosthenes, a bitmap is 7-9 times slower than for multiples, but for Atkin only 50% or so. There is not much difference between 8, 16, 32 and 64 bit integral types, possibly somewhat slower for the larger ones.