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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.