Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 40 down vote accepted

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.

share|cite|improve this answer
2  
It should be noted that this is derived from the prime number theorem. – BlueRaja - Danny Pflughoeft Jul 30 '10 at 20:40
    
Right. I had omitted mentioning it, but thanks to your reminder I went and found a precise bound I hadn't previously seen. :-) – ShreevatsaR Jul 30 '10 at 20:58
    
Why the downvote? – ShreevatsaR Sep 21 '14 at 18:30
    
I don't know why the downvote, but a closely related question was just posted (math.stackexchange.com/questions/940338/…) and perhaps it has gotten this topic some new attention. (I think your first sentence is a good summary conclusion, but someone else may disagree.) – David K Sep 22 '14 at 20:34

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.

share|cite|improve this answer
    
Note that this 26-variable polynomial isn't well suited to generate primes, as most of its codomain is negative. – stevenvh Aug 7 '10 at 17:39
    
I remember it was presented to us in the elementary course of number theory, and I think the teacher said that after much work they managed to reduce it to 22 variables. – Asaf Karagila Sep 11 '10 at 17:59
7  
This 26-variable polynomial still gives me the creeps. I find it very strange indeed. – Sputnik Jun 7 '11 at 22:45

Far better than sieving in the large range ShreevatsaR suggested (which, for the 10^15-th prime, has 10^15 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^8 or 10^9, 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.

share|cite|improve this answer
    
Thanks. I've updated my answer to not recommend sieving. – ShreevatsaR Sep 9 '10 at 7:30
2  
@ShreevatsaR: Don't get me wrong -- your answer is far better than the naive method of stepping through numbers and testing them! I was just suggesting an improvement. :) – Charles Sep 9 '10 at 18:55
    
"At this point you can sieve the small distance, perhaps just 10^8 or 10^9, to the desired number." How would you recognize this number? – Liviu Jan 17 at 15:00
    
@Liviu: Suppose you want the millionth prime and you find an $x$ with 998,000 primes less than it. You just need to "count up" 2000 primes. The expected length needed is then about $2000\log x$, but you should probably add, say, 10% or so in case the primes don't cooperate. – Charles Jan 18 at 9:47
    
@Charles I know the 1000000th prime because I know the 998000th prime because I know the 996000th prime ... because I know the 20th prime, that's 71. It seems easy now ... oh, wait a minute – Liviu Jan 21 at 21:59

No such formula is known, but there are a few that give impressive results. A famous one is Euler's: $$P(n) = n^2 − n + 41$$ Which yields a prime for every natural number lower than $41$, though not necessarily the $n$th prime.

See more here.

share|cite|improve this answer

The one I like best is: $$ p_n=1+\sum_{r=1}^{2^n}\left\lfloor \sqrt[n]{n}-\sqrt[n]{\sum_{s=1}^{r}\left(\cos\left(\pi\frac{(s-1)!+1}{s}\right)\right)^2}\right\rfloor $$

share|cite|improve this answer
    
Which says that $p_1 = 0$, $p_2 = -1$, $p_3 = -4$, $p_4 = -11$, $p_5 = -26$... – Winther Mar 9 at 20:03

Yes, there is an explicit formula for the nth prime number published by Mr. A.Venugopalan in the Proceedings of Indian Academy of Sciences in 1983. Here it is:

$$P_{n + 1}^2{\rm{ = 1 + }}\left| {{\rm{ }} - {{\log }_X}\left( {\raise.5ex\hbox{$\scriptstyle 1$}\kern-.1em/ \kern-.15em\lower.25ex\hbox{$\scriptstyle 2$} {\rm{ }}\sum\limits_{{a_1} = 1}^{{p_1} - 1} {...\sum\limits_{{a_n} - 1}^{{p_n} - 1} {\sum\limits_{b = 1}^n {{X^{ - {{\left( {\sum\nolimits_1^n {{a_i}{Q_i} - bQ} } \right)}^2}}}} } } - {\rm{ 1/X }}} \right)} \right| % MathType!MTEF!2!1!+- % feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0dg9Lq-Fc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaaDa % aaleaacaWGUbGaey4kaSIaaGymaaqaaiaaikdaaaGccaqGGaGaaeyp % aiaabccacaqGXaGaaeiiaiaabUcajqgaacGaaeiiaOWaaqWaaKazaa % sabaGaaeiiaiabgkHiTiGacYgacaGGVbGaai4zaOWaaSbaaKazbaka % baGaamiwaaqcbaAabaGcdaqadaqcKbaWaeaajqgaaeaeaaaaaaaaa8 % qacaGG9cGaaeiiaOWaaabCaeaacaGGUaGaaiOlaiaac6cadaaeWbqa % amaaqahabaGaamiwamaaCaaaleqabaGaeyOeI0YaaeWaaeaadaaeWa % qaaiaadggadaWgaaadbaGaamyAaaqabaWccaWGrbWaaSbaaWqaaiaa % dMgaaeqaaSGaeyOeI0IaamOyaiaadgfaaWqaaiaaigdaaeaacaWGUb % aaoiabggHiLdaaliaawIcacaGLPaaadaahaaadbeqaaiaaikdaaaaa % aaWcbaGaamOyaiabg2da9iaaigdaaeaacaWGUbaaniabggHiLdaale % aacaWGHbWaaSbaaWqaaiaad6gaaeqaaSGaeyOeI0IaaGymaaqaaiaa % dchadaWgaaadbaGaamOBaaqabaWccqGHsislcaaIXaaaniabggHiLd % aaleaacaWGHbWaaSbaaWqaaiaaigdaaeqaaSGaeyypa0JaaGymaaqa % aiaadchadaWgaaadbaGaaGymaaqabaWccqGHsislcaaIXaaaniabgg % HiLdqcKbaWa8aacqGHsislcaqGGaGccaqGXaGaae4laiaabIfajaa4 % peGaaeiiaaGcpaGaayjkaiaawMcaaaqcKbaaciaawEa7caGLiWoaaa % a!8140! $$

Where X is any given positive number.

share|cite|improve this answer
4  
What are $Q$ and the $Q_t$? What are the $p_i$? Why is this expression independent of $X$? – anomaly Jul 10 '15 at 2:38

protected by Community Mar 20 at 3:14

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?