about prime number generation

[Adrien Prost-Boucle]

Or, probably better for storage and coding time, slightly less good for rapidity:
Pre-list all primes up to sqrt(10^10), there are <10k, listed in no time
Then write a tiny nextprime() function that would just test divisibility by those.
(or implement a segmented sieve of Eratosthenes from there, slightly more code)

Regards,
Adrien


On Thu, 2022-05-19 at 23:41 +0200, Adrien Prost-Boucle wrote:
> 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
> > 
>