The *n*th prime is approximately *n* log *n*.

For more precise estimates, there are numerous upper and lower bounds for the *n*th prime, each tighter over some intervals than others. Here I want to point out upper and lower bounds from a dissertation by Christian Axler on page viii.

First, define

Then for sufficiently large *n*, the *n*th prime number, *p*_{n}, is bounded above and below by

The lower bound holds for *n* ≥ 2, and the upper bound holds for *n* ≥ 8,009,824.

For example, suppose we want to estimate the 10 millionth prime. The exact value is 179,424,673. The bounds we get from the equations above are 179,408,030 and 179,438,842.

The width of the bracket bounding *p*_{n} is 0.787 *n* / log²*n*. In our example, the difference between the upper and lower bounds is 30,812.

This width, relative to *p*_{n}, decreases something like *O*(1/log³ *n*). In our example, the width of the bounding interval is 0.017% of *p*_{n}.

So all things live in a prime interval. What would the cost of crossing into the next prime interval be?

David, what do you mean by cost? The width of an interval is given by the difference f(n+1) – f(n). That width is twice the maximum distance of a point to the border of “its” interval.