Does anyone knows how exactly Prime works ?

For example how Prime[1000000000] is calculated ?

The only information I found was some inequalities in Wolfram's Function site.

Thank you.

  • 3
    $\begingroup$ Possible duplicate: What is so special about Prime?. Implementation notes state only: "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." $\endgroup$
    – Mr.Wizard
    Dec 17, 2013 at 12:06
  • 2
    $\begingroup$ What you ask here in principle you can find in the links provided by Mr.Wizard. I asked there a bit more general question, however the answers provided were not fully explanatory. This is the case here as well, since you'll have to study the Lagarias-Miller-Odlyzko paper which is crucial for understanding how PrimePi works. Then Prime could be implemented e.g. this way: prime[z_Integer] /; z >= 1 := x /. First @ Solve[PrimePi[x] == z && PrimePi[x - 1] == z - 1, x, Integers] $\endgroup$
    – Artes
    Dec 17, 2013 at 12:31