2

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.

2

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

Possible duplicate: What is so special about Prime?. Implementation notes state only: "

– Mr.Wizard – 2013-12-17T12:06:42.260`Prime`

and`PrimePi`

use sparse caching and sieving. For largen, the Lagarias-Miller-Odlyzko algorithm for`PrimePi`

is used, based on asymptotic estimates of the density of primes, and is inverted to give`Prime`

."2What 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]`

– Artes – 2013-12-17T12:31:26.493