nth_prime
Niels Möller
nisse at lysator.liu.se
Tue May 21 18:49:44 UTC 2019
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.
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.
More information about the gmp-devel
mailing list