# Determine nth prime number in O(?)

If f(n) is the problem to determine the nth prime number, how fast can this be done, i.e.

• What is the fastest known algorithm to find the nth prime number?
• What are lower bounds for the time complexity?
• These problems are incredibly well-studied. What research have you done? I'd expect that even Wikipedia should have a wealth of information. – Raphael Nov 1 '16 at 11:52
• @Raphael I am sorry, but I was looking for a plain and simple answer (like: The problem can be solved in n^2 log n ) and could not find it on the net. – J. Fabian Meier Nov 2 '16 at 9:05

For upper bounds, see this question on math.se. Apart from a few trivial cases, we don't know how to prove any meaningful lower bounds on general computation models, and in particular for this problem.

You can calculate π (N) = the exact number of primes ≤ N in about O (N^(2/3)), give or take a logarithm, without any really difficult mathematics (google for Lagarias Miller Odlyzko algorithm); there are faster methods that are hard.

Find a suitable function for estimating the value of the n-th prime, say the n-th prime is roughly around X (constant time). Count the number of primes ≤ X (roughly O (X^(2/3))) which should be some n' close to n. If n' is too far away from n then you use it to get a better estimate X'. If n' is close to n then you create a sieve that includes the number X and is big enough to include the n-th prime.

Answer of both questions depends on what kind of solution you want. That is if you want an exact solution you can use Sieve of Eratosthenes algorithm which has a time complexity of $O(n \log \log n)$. If you want an approximate solution then you can use an approximation algorithm for primality testing (see Wikipedia). This algorithm has a time complexity of $O(n/(\log n)^2)$ which is sublinear.

• There are also methods based on computing $\pi$, the prime counting function. See the answers to the question mentioned in my answer. – Yuval Filmus Nov 1 '16 at 9:52
• Careful: Eratosthenes can count the primes ≤ n. However, you want the n-th prime which will be very roughly around n log n, so you need a sieve of size n log n or so, which will take about O (n log n). – gnasher729 Nov 1 '16 at 16:48
• Using a sieve for the nth prime is easy to understand and code, and a fine solution for tiny inputs. But it's nowhere close to the fastest algorithm for the task. What is a "approximation algorithm for primality testing"? The link goes to nth prime approximations, which looks like O(log log n) for the simpler formulas -- essentially a small constant time for sub million-digit inputs. The logarithmic integral or Riemann's R function would take longer, but not a lot more. – DanaJ Dec 30 '16 at 18:18