Is there a known mathematical equation to find the nth prime?

I've solved for it making a computer program, but was wondering there was a mathematical equation that you could use to solve for the nth prime?

Solution 1:

No, there is no known formula that gives the nth prime, except artificial ones you can write that are basically equivalent to "the $n$th prime". But if you only want an approximation, the $n$th prime is roughly around $n \ln n$ (or more precisely, near the number $m$ such that $m/\ln m = n$) by the prime number theorem. In fact, we have the following asymptotic bound on the $n$th prime $p_n$:

$n \ln n + n(\ln\ln n - 1) < p_n < n \ln n + n \ln \ln n$ for $n\ge{}6$

You can sieve within this range if you want the $n$th prime. [Edit: There are better ideas than a sieve, see the answer by Charles.]

Entirely unrelated: if you want to see formulae that generate a lot of primes (not the $n$th prime) up to some extent, like the famous $f(n)=n^2-n+41$, look at the Wikipedia article formula for primes, or Mathworld for Prime Formulas.

Solution 2:

Far better than sieving in the large range ShreevatsaR suggested (which, for the 10¹⁵th prime, has 10¹⁵ members and takes about 33 TB to store in compact form), take a good first guess like Riemann's R and use one of the advanced methods of computing pi(x) for that first guess. (If this is far off for some reason—it shouldn't be—estimate the distance to the proper point and calculate a new guess from there.) At this point, you can sieve the small distance, perhaps just 10⁸ or 10⁹, to the desired number.

This is about 100,000 times faster for numbers around the size I indicated. Even for numbers as small as 10 to 12 digits, this is faster if you don't have a precomputed table large enough to contain your answer.

Solution 3:

There are formulas on Wikipedia, though they are messy. No polynomial $p(x)$ can output the $n$th prime for all $n$, as is explained in the first section of the article.

There is, however, a polynomial in 26 variables whose nonnegative values are precisely the primes. (This is fairly useless as far as computation is concerned.) This comes from the fact that the property of being a prime is decidable, and the theorem of Matiyasevich.