1
$\begingroup$

$n\ln n + n\ln\ln nāˆ’n < p_n < n\ln n+n\ln\ln n \mbox{ for } n\geq 6$

This is the range where the $n$-th prime must lie. However sieving within this range generates a large number of primes. So if one is asked to, for example, find the 48574th prime, how does one go about it?

I was able to find the relevant prime by using an implementation of the sieve algorithm, checking only till the square root of the given number. However the method described above takes merely an instant to give a list of possible candidates and the correct answer also lies in them, but I am unable to pinpoint the primes as 'nth' or 'mth'.

  • 0
    @PeterPhipps My bad. Corrected. – 2012-04-09

1 Answers 1

2

There are asymptotically fast methods of computing $\pi(x)$, the number of primes less than or equal to x. So compute a guess of the size of the n-th prime by inverting the logarithmic integral, then count the number of primes up to that point.

If the count is very far from n (in practice, this probably won't ever happen), take the density of primes in the location of your guess and the number of primes you are off by and find a new estimate, returning to the first step to compute it.

If the count is almost exact, test numbers with a primality test until you get to the right count.

Otherwise, sieve the area below/above your guess (as appropriate based on the number of primes you found) until you find the right count.

  • 0
    @Srijan: You can avoid counting them from 1 by using the technique I outlined in my answer, which requires an advanced algorithm like that of Lagarias, Miller, & Odlyzko for computing the number of primes up to a given bound. This can drop the complexity from $n\log n/\log\log n$ (sieve up to the n-th prime with the Atkin-Bernstein sieve) to $O(n^{2/3+\varepsilon})$ (LMO algorithm applied a logarithmic number of times) or even $O(n^{1/2+\varepsilon})$ (analytic method applied a logarithmic number of times). – 2012-04-09