# 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

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.
• @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