# 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

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