-1
$\begingroup$

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?
$\endgroup$
  • 2
    $\begingroup$ These problems are incredibly well-studied. What research have you done? I'd expect that even Wikipedia should have a wealth of information. $\endgroup$ – Raphael Nov 1 '16 at 11:52
  • $\begingroup$ @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. $\endgroup$ – J. Fabian Meier Nov 2 '16 at 9:05
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There are also methods based on computing $\pi$, the prime counting function. See the answers to the question mentioned in my answer. $\endgroup$ – Yuval Filmus Nov 1 '16 at 9:52
  • $\begingroup$ 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). $\endgroup$ – gnasher729 Nov 1 '16 at 16:48
  • $\begingroup$ 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. $\endgroup$ – DanaJ Dec 30 '16 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.