about prime number generation

[Adrien Prost-Boucle]

Hi Enrique,

Expectations is subjective, could you illustrate with run times that
would fit your objectives ?

To my eyes (and for gmp too) 10^10 is really small number for example
;-)
Around 10^10, this is roughly the 450 million-th, which is found in 20
msec on my laptop.

On the other side, the 450 million first primes are found in 20 minutes
on the same machine (personal code, certainly not optimal)
If your application requires super-fast repeated query of nth prime, a
very effective solution could be to invest 20 min / 1 h once and pre-
list all primes in the range of interest.
It would fit in a few GBs or RAM with numbers represented by range (and
even less on disk with compression).

Regards,
Adrien


On Thu, 2022-05-19 at 18:59 +0000, Garcia Moreno-Esteva, Enrique wrote:
> Hi Adrien,
> 
> 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. I have
> put this project on hold, since I was also working with another math
> project involving prime numbers which is going much better.  But I
> will return to it, perhaps in a month or two.
> 
>  Regards,
> Enrique
> 
> Get Outlook for iOS
> From: Adrien Prost-Boucle <adrien.prost-boucle at laposte.net>
> Sent: Thursday, May 19, 2022 9:39:48 PM
> To: Garcia Moreno-Esteva, Enrique <enrique.garciamoreno-
> esteva at helsinki.fi>; gmp-discuss at gmplib.org <gmp-discuss at gmplib.org>
> Subject: Re: about prime number generation 
> Hi Enrique,
> 
> As far as I know, GMP does not at the moment implement what you are
> looking for.
> The best I know is the following (has already been mentioned a bit in
> the past in this mailing list) :
> https://github.com/kimwalisch/primecount
> 
> Curiosity question :
> Did you already experiment with the project above, would there be a
> property of it that makes you want to look elsewhere too ?
> 
> Regards,
> Adrien
> 
> 
> On Sat, 2022-04-30 at 12:31 +0000, Garcia Moreno-Esteva, Enrique
> wrote:
> > Hello,
> > 
> > I apologize this is not a comment about your webpage, but more a
> question about your library. Would your library contain a function
> (call it p(n) ) that generates the n-th prime? If it does not,
> alternatively, do you have a lower bound for  certifiably producing
> the next prime with the nextprime function in your library (it is
> probabilistic, but such probabilistic methods are deterministic below
> certain bounds, so my question is, what is the lower bound for your
> function)?
> > 
> > I thank you in advance for your help.
> > 
> > Enrique Garcia Moreno-Esteva
> > 
> > _______________________________________________
> > gmp-discuss mailing list
> > gmp-discuss at gmplib.org
> > https://gmplib.org/mailman/listinfo/gmp-discuss
>