about prime number generation

[Hans Åberg]

> On 4 Jun 2022, at 11:39, Marco Bodrato <bodrato at mail.dm.unipi.it> wrote:
> 
> 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
> 
> For sure, it did not sieve all the primes up to 10^15; the very fast primecount program (by Kim Walisch) needs more time to simply count them all :-)

I made some timings on a MBP 2.4 GHz, up to 10¹¹, and it is linear 𝒪(𝑛) with measured time about 21𝑛 ns. For the range 10¹²–10¹²+10¹¹, the time is about 26𝑛 ns with the interval size 𝑛 = 10¹¹. And it does not use much memory. It means that 𝑛 = 10¹² would take about 5.8 hours. But it runs in only one thread, so eventual parallelization might reduce that.

primegen-0.97 % time ./primes 1 100000000000 | openssl sha3-256
SHA3-256(stdin)= 2143522c6172590ab377e9a19649cfcc55305f4fb020cda23a50678c3cf57f9e
./primes 1 100000000000  2102.12s user 19.70s system 96% cpu 36:33.87 total

primegen-0.97 % time ./primes 1000000000000 1100000000000 | openssl sha3-256
SHA3-256(stdin)= 9042899f10d0923b5538577d6c015546dda5f285a3718462efb2d8414bb8fe93
./primes 1000000000000 1100000000000  2630.41s user 14.32s system 98% cpu 44:39.89 total