3
$\begingroup$

Assume we had an exact formula for $\pi (n)$, how could we get from that formula an exact expression for the $n$th prime?
I tried looking at approximations we have of $\pi (n)$ like $\frac {n}{\ln (n)}$, and from that I was able to state an approximation for the $n$th prime as $n \ln (n)$, which, with the previous definition, could be expressed as $\frac{n^2}{\pi (n)}$ but this does not seem correct.
If we had a correct expression for $\pi (n)$, how could we calculate the $n$th prime as a function of $\pi (n)$?

$\endgroup$
2

1 Answer 1

4
$\begingroup$

Maybe it's too late, But I think I should answer this.

Now if you're trying to compute the nth prime, it has been proven that the nth prime must be greater than

nlog(n)+n(loglog(n))−1)

and less than

nlog(n)+nlog(log(n))

When n≥6. So if you're searching for the nth prime, you can use these ranges to search the nth prime number. Here you can use binary search to get the nth Prime number.

l = n * log(n) + n*(log(log(n))-1);
u =  n * log(n) + n*log(log(n));
while(l != u){ 
    m = l + (u - l) /2;
    if(pi(m) >= n) u = m; 
    else l = m + 1; 
}

so m will me the prime number you are looking for.

where pi(m) is prime count function (number of primes less than m).

I use above concept to solve on SPOJ problem. http://www.spoj.com/problems/NTHPRIME/

$\endgroup$
1
  • 2
    $\begingroup$ The downside is that as n becomes larger, it becomes much cheaper to use a better starting estimate and sieve the small difference, versus repeatedly calling prime count. SPOJ uses small values for n, but even at 10^9 there would be a pretty big performance difference. The faster way is described in the math.stackexchange link. $\endgroup$
    – DanaJ
    Aug 1, 2017 at 16:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .