nth_prime

[Laurent Desnogues]

On Tue, May 21, 2019 at 8:49 PM Niels Möller <nisse at lysator.liu.se> wrote:
>
> Seth Troisi <braintwo at gmail.com> writes:
>
> > 3. Use Legendre's Formula (github
> > <https://github.com/sethtroisi/libgmp/pull/9>)
>
> Any reference for this method? I've never read anything about efficient
> computation of the nth prime. A web search turns up this sketch:
> https://programmingpraxis.com/2011/07/22/counting-primes-using-legendres-formula/,
> but it's not clear to me for how large sizes it is practical.

There's a very fast program for computing \pi(x), which includes
references and comparisons of methods:

https://github.com/kimwalisch/primecount

HTH,

Laurent

> It seems clear that an efficient nth prime can be implemented on top of
> an efficient \pi(k) = (number of primes <= k): Given n, first find some
> k such that \pi(k) \approx n, e.g., based on asymptotics and/or binary
> search. Next, compute \pi(k) exactly. Then enumerate primes close to k
> (sieving + primality tests) to identify the nth prime.
>
> Regards,
> /Niels
>
> --
> Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
> Internet email is subject to wholesale government surveillance.
> _______________________________________________
> gmp-devel mailing list
> gmp-devel at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-devel