about prime number generation

[Hans Åberg]

The program does not compute the primes, just counts them, unless one asks it to do that, and then it takes much longer time, or so it seems.

I was able to compute the original question, 𝑝(10¹²):
primesieve % time ./primesieve 1e12 --nth-prime
Sieve size = 128 KiB
Threads = 8
Seconds: 2931.324
Nth prime: 29996224275833
./primesieve 1e12 --nth-prime  21309.71s user 80.26s system 729% cpu 48:51.34 total

The function primesieve uses the Eratosthenes sieve with time complexity 𝒪(𝑛 log log 𝑛) and is parallelized, so it could be that parallelizing the Atkin sieve program, which has time complexity 𝒪(𝑛), gives some gains.

The value 𝜋(10²⁹), as in the table at [1], was according to [2] computed with the primecount program using two AMD EPYC 7642 CPUs with a total of 96 CPU cores (192 threads); there is a picture of it at [3].

Interestingly according to the following comment at [2], for this value, the Riemann function is considerably closer than that of Li(𝑥). Perhaps they can be used to zoom into a small interval to sieve.

1. https://en.wikipedia.org/wiki/Prime-counting_function
2. https://www.mersenneforum.org/showthread.php?p=601119
3. https://github.com/kimwalisch/primecount/blob/gh-pages/images/AMD-Rome-Server.jpg


> On 5 Jun 2022, at 21:04, Seth Troisi <braintwo at gmail.com> wrote:
> 
> Kim Walisch also has a primesieve library which is more of a fair
> comparison than primecount (which doesn't take an optional start)
> 
> At 1e4 we're probably measuring disc latency, process creation, ..., memory
> allocs, ...
> I have to sieve up to 1e9 primes on my system to take > .1 seconds
> 
> ```
> $  ./primesieve -t1 1e15-1e4 1e15
> Seconds: 0.019
> Primes: 268
> 
> $ ./primesieve -t1 1e15-1e9 1e15
> Seconds: 0.373
> Primes: 28954129
> 
> $ time ./primes 999999999990000 1000000000000000|wc
> 268     268    4288
> real 0m0.477s
> 
> $ time ./primes 99999990000000 1000000000000000|wc
> 28954129 28954129 463266064
> real 1m48.190s
> ```
>