# Numbering primes within a range.

$$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'.

• If I'm reading this right, with $n=48574$, your expression is $634973 \lt p_n \lt 639697$ but according to Wolfram Alpha the 48574th prime is 593059. There isn't a way of pin-pointing the $n$th prime and sieving a range of values is much faster than checking individual numbers, even if it does generate 48573 primes you're not interested in. – Peter Phipps Apr 9 '12 at 13:47
• Well in that case I guess I will have to stick to sieving algorithms and improvements on them. – Srijan Apr 9 '12 at 14:03
• @PeterPhipps Pardon me for having used an example which didn't quite tally. The 10001st prime (yes, Project Euler sent me here) lies within the predicted range. I managed to get the answer using a sieving method. However the range that was predicted did contain the 10001st prime and did not take more than instant to calculate. That, though , didn't get me anywhere, hence the question. I have not found any other answers either, seemingly the range prediction is just that, and cannot be used for numbering primes? – Srijan Apr 9 '12 at 14:29
• I've just looked closer at this and I think the bracketing on the left hand side of your expression isn't quite right. It should be $n(ln(n))+n(ln(ln(n))−1)$, in which case the lower bound is 591123 which is a lot better. When I solved that Euler problem I found (using a sieve) the primes below 200000 although I can't remember why I chose that number. – Peter Phipps Apr 9 '12 at 15:03
• @PeterPhipps My bad. Corrected. – Srijan Apr 9 '12 at 16:12

## 1 Answer

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.

• Alternately, if you only need to find small primes, just use a sieve to locate all primes up to the high end of the estimate, then step through them until you see n of them. – Charles Apr 9 '12 at 15:24
• I did use this suggestion in another question where I had to find the sum of primes below a certain number. I found the primes in the neighbourhood of that number and hence managed to save on quite a bit of calculation there. However when it comes to numbering them I have to start from 1 anyway right? Or am I mistaken? – Srijan Apr 9 '12 at 16:23
• @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). – Charles Apr 9 '12 at 16:57