about prime number generation

[Marco Bodrato]

Ciao Seth,

Il 2022-04-30 23:39 Seth Troisi ha scritto:
> I worked on nth_prime(n) in a series of patches three years ago

That code was very interesting.
It would be nice to get rid of the double type and the function log(). 
The library is not using math.h and libm anywhere now. But it doesn't 
seem simple, at least for me.

We should start pushing a primepi(N) function, counting the primes 
between 1 and N.
I have a function, which is almost ready, with the following prototype:
long gmp_pi_ui (unsigned long n)

But to have a function that really belongs to GMP, we should extend it 
to at least mpz_pi (mpz_t n) ... With a reasonable return type ...

> Sadly this never made it upstream as the review process for a faster
> next_prime took up all of my energy

We should further improve that work!

With your improvements to nextprime, it's really a waste of resources if 
ones have to write
   for (int i = 0; i < delta2; i++)
     mpz_nextprime(p, p);
because every sieved range is used just once, instead of scanning it to 
the end.

I mean, we should add a couple of (public or not?) functions:
  mpz_nth_{prec,next}prime

> In practice I'd recommend you also take a look at the
> highly optimized code from kimwalisch
> https://github.com/kimwalisch/primecount

Of course a specialized library will remain faster than some small piece 
of code in GMP...

Ĝis,
m