# How does Mathematica calculate the nth prime?

When I enter Prime[2000000000000], the two-trillionth prime, Mathematica gives 61427839512211 for the answer after several minutes of calculation.

I wonder how it calculates to get this number. Apparently, it does not pull that number out from a list, since it spends several minutes to get the answer.

-

## 1 Answer

Prime and PrimePi use sparse caching and sieving. For large $n$, the Lagarias-Miller-Odlyzko algorithm for PrimePi is used, based on asymptotic estimates of the density of primes, and is inverted to give Prime.

-
I believe community wiki abuse is mentioned as a scientific perversion somewhere in the Marquis de Sade complete works. – Dr. belisarius May 24 '13 at 20:21
@bel, I would have left it as a comment, but it was too damn long. :P – J. M. May 25 '13 at 1:29