about prime number generation

[Marco Bodrato]

Ciao,

> On Thu, 2022-05-19 at 18:59, Garcia Moreno-Esteva, Enrique wrote:
>> Thank you for writing.  Yes, I have looked into it. It is not
>> that fast once you get to really larger numbers, say past 10^10.

Well, I'm sure that the implementation that we could add to GMP would 
not be faster :-/

Il 2022-05-19 23:41 Adrien Prost-Boucle ha scritto:
> To my eyes (and for gmp too) 10^10 is really small number
> for example ;-)

If you put 10^10 in an mpz_t variable and use it for simple arithmetic, 
I agree, that's small for GMP.

But if you set an unsigned long to 10^10, and use it as the parameter 
for some functions internally using primes... it's not that small.
Think to the following function calls:
   mpz_fac_ui (z, 10000000000);
   mpz_primorial_ui (z, 10000000000);
   mpz_bin_ui (z, z, 10000000000);

> Around 10^10, this is roughly the 450 million-th, which is
> found in 20 msec on my laptop.

My code is some 50 times slower, and probably even worse when the size 
grows.

> On the other side, the 450 million first primes are found
> in 20 minutes on the same machine (personal code,

There's a function for sieving in the file primesieve.c.
It needs a pointer to (10000000000/3/GMP_LIMB_BITS)+1 limbs, then

gmp_primesieve (pointer_to_sieve, 10000000000);

should sieve the 0..10000000000 range (with the Erathostenes' sieve) in 
some tenths of seconds.

It does not generate the list of primes, but a compact bitmap.

And of course, the multi-threaded primesieve (by the same author of 
primecount) is even faster :-)

Ĝis,
m

-- 
http://bodrato.it/papers/