about prime number generation

Hans Åberg haberg-1 at telia.com
Fri May 20 14:31:32 CEST 2022


> On 30 Apr 2022, at 14:31, Garcia Moreno-Esteva, Enrique <enrique.garciamoreno-esteva at helsinki.fi> wrote:
> 
> 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)?

Some inputs:

Page that mentions Sieve of Atkin that runs in O(n) time, better than Eratosthenes O(n log log n):
https://www.baeldung.com/cs/prime-number-algorithms
https://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf

Also see the article:
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
https://wiki.haskell.org/Prime_numbers

For large numbers, there is suggestion here to start with a guess and find an exact value for a nearby value, and then sieve to the asked for value, but I am not sure how this works in practise:
https://math.stackexchange.com/questions/1257/is-there-a-known-mathematical-equation-to-find-the-nth-prime

Programs that implements it using a sieve:
https://stemhash.com/how-to-find-the-nth-prime-number/
https://www.geeksforgeeks.org/program-to-find-the-nth-prime-number/amp/




More information about the gmp-discuss mailing list