about prime number generation

[Marco Bodrato]

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

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 :-)

~/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.

I installed the pre-packaged program for my Linux distribution, and I 
see:

~/src/primegen-0.97$ ldd $(which primecount)
	linux-vdso.so.1 (0x00007ffe591f1000)
	libprimecount.so.7 => /lib/x86_64-linux-gnu/libprimecount.so.7 
(0x00007f3589249000)
	libprimesieve.so.9 => /lib/x86_64-linux-gnu/libprimesieve.so.9 
(0x00007f3589212000)
[...]

~/src/primegen-0.97$ ls -lL 
/lib/x86_64-linux-gnu/libprime{count,sieve}.so.?
-rw-r--r-- 1 root root 383032 Maj  8 16:22 
/lib/x86_64-linux-gnu/libprimecount.so.7
-rw-r--r-- 1 root root 219168 Maj  8 14:04 
/lib/x86_64-linux-gnu/libprimesieve.so.9

~/src/primegen-0.97$ ls -lL /lib/x86_64-linux-gnu/libgmp.so.10
-rw-r--r-- 1 root root 525152 Nov 15  2021 
/lib/x86_64-linux-gnu/libgmp.so.10

Counting both libraries needed by primecount, they are larger than the 
full GMP library.

Ĝis,
m