4
$\begingroup$

Say I want to find the n-th prime. Is there an algorithm to directly calculate it or must I do with sieving? I know always calculate the next prime with a sieve principle, but what if I want the n-th prime?

Duplicate:

https://math.stackexchange.com/questions/1257/is-there-a-known-mathematical-equation-to-find-the-nth-prime

$\endgroup$
  • 5
    $\begingroup$ How big is $n$? $\endgroup$ – Dave Clarke Mar 21 '13 at 14:24
  • 3
    $\begingroup$ This is a very well studied problem. What kind of research have you done yourself? $\endgroup$ – Raphael Mar 21 '13 at 14:32
  • 5
    $\begingroup$ Why have you posted a C program? It doesn't add anything to the question. In any case, this will only work up-to primes that fit in 32 (or 64) bits. $\endgroup$ – Dave Clarke Mar 21 '13 at 16:11
  • 1
    $\begingroup$ As a practical solution, how about storing the primes in a lookup table. This way you can get the $n$th prime in $O(1)$ time. $\endgroup$ – Juho Mar 21 '13 at 22:51
  • 1
    $\begingroup$ No, just check what the largest prime that your $b$-bit integer can hold is. Let $p$ be this prime. The size of the table is then $\pi(p)$, where $\pi$ is the prime counting function. $\endgroup$ – Juho Mar 22 '13 at 4:35
14
$\begingroup$

What do you mean by "directly"? This is not well-defined. Arguing that an algorithm doesn't do something during its computation is not a nice well-defined concept (when that something is a semantic condition).

It is probably one of the most common mistakes that people make when thinking about algorithms because they look at obvious cases and think it is simple to formalize the concept that algorithms for a problem does performs some task like computing some other things during its computation but that is not simple at all!

Moreover why would we care? What we care about in practice is not that the algorithm computes all previous primes, but rather time and space efficiency. So I guess a better way of asking your question is asking if there is more efficient way of computing $n$th prime number than sieve-based methods.

If you are asking if there is a provably correct and efficient algorithm to find $n$th prime given $n$ in binary the answer is that is an open question. We don't know if there is any such algorithm, and we don't know if there isn't one. AFAIK, it is consistent with our current state of knowledge that there are algorithms for generating the $n$th prime that run in linear time in $n$. In fact, it can even be the case that we can generate the $n$th prime from bits of $n$ using a polynomial-size constant-depth circuit with threshold gates ($\mathsf{TC^0}$), in simplified non-technical terms: there can be a parallel algorithm with polynomial number of processors that generates the $n$th prime number in constant time and each processor computes very simple functions. So there is big gap between algorithms that we have (upper-bounds) and lower-bounds we can prove for the problem.

However we have algorithms that work efficiently and correctly assuming conjectures like conjectures about how primes are distributed.

See the Wikipedia article on generating prime numbers if you haven't. Also you may want to check this question: Which is the fastest algorithm to find prime numbers?

$\endgroup$
  • $\begingroup$ I mean like there is a formula for the n-th digit of pi and that was recently discovered(?) $\endgroup$ – Niklas Rosencrantz Mar 31 '13 at 23:05
  • $\begingroup$ @Ncik, what you mean by "formula"? $\endgroup$ – Kaveh Mar 31 '13 at 23:52
  • $\begingroup$ mamnoon jaleb bood $\endgroup$ – M a m a D Nov 19 '15 at 6:03
4
$\begingroup$

When $n$ is not big, then I think the sieve-based algorithms perform well. We just need to keep a list of size $O(n \log n)$ and run one of a well-known sieve-based algorithms for generating primes.

When $n$ is big and we can't afford to keep a list of size $O(n \log n)$, we can use an in-place sieve method. But I personally prefer to have a small list of primes and use Miller-Rabin test to iterate through possible primes.

The sieve-based algorithms are the most efficient algorithms we currently know for generating prime numbers.

It is not clear what you mean by generating $n$th prime "directly". If you mean that there is any known algorithms as fast as sieve-based algorithms for generating the $n$th prime number that doesn't compute the previous primes numbers then the answer is that we don't know any such algorithm.

If by "direct" you mean a polynomial in one variable that gives the $n$th prime number, then we can actually prove that there is no polynomial function with integer coefficient for calculating nth prime number. And even if there was such a polynomial the algorithms for evaluating polynomials use $\Omega(\log m)$ operations where $m$ is the power of the polynomial to be evaluated.

Note that although we have efficient algorithms for testing primality of a given number (e.g. AKS which is polynomial-time) they don't give an algorithm for finding primes.

P.S: Here you can find a good implementation of Miller-Rabin test, which can be extended to arbitrary large numbers.

$\endgroup$
  • 3
    $\begingroup$ "There is no direct way to find nth prime number(actually is impossible)". This is patently false. Since there are infinite primes, the nth one always exists. Since primality testing is solveable, you can simply iterate through each number, tset if it's prime, and increase your count of primes until you have found the nth one. $\endgroup$ – jmite Mar 22 '13 at 1:46
  • 1
    $\begingroup$ @jmite, what? iterating is direct way? first of all at least read my answer, second I suggested iterating but it's not direct way, because before you find nth prime (for $n>n_0$) you should find kth prime number such that $k<n$, So is not direct. If primary testing like AKS is in $P$ doesn't mean finding nth prime is $O(1)$, if you could do it even in $P$ you will be fabulous millioner. $\endgroup$ – user742 Mar 22 '13 at 8:40
  • $\begingroup$ I did the edit so I am removing my previous comments which do not apply anymore. Feel free to roll back or edit further. $\endgroup$ – Kaveh Mar 22 '13 at 15:24
  • $\begingroup$ It is much clearer now, I had misinterpreted your answer as saying that the nth prime is actually incomputable. $\endgroup$ – jmite Mar 22 '13 at 20:24
  • $\begingroup$ Sieve is the fastest for generating the first n primes, but not by a long shot to generate just one prime (the n-th one). $\endgroup$ – gnasher729 Nov 30 '16 at 9:27
1
$\begingroup$

The cop-out but realistic answer for small inputs would be $O(1)$ for tiny inputs and roughly $O(\log n)$ below some finite threshold as it can be done as a binary search through a table of primes. Since we can get good starting bounds it might be even smaller -- our search range is a small fraction of the table.

What is often done for medium sizes, say 100k to 100M, is sparse tables followed by sieving the range between entries. With enough entries the sieving doesn't take long, so the result is pretty fast and even 1k of tables plus a decent sieve takes you to 100M or so. It doesn't scale well however. I know one application that does this for large sizes at the expensive of ridiculous amounts of table storage, but was also done before open source implementations of the next paragraph were available.

Beyond these toy input sizes, we can do a binary search on the prime count. The extended LMO method is complexity $O\big(\frac{x^{2/3}}{\log^2{n}}\big)$. I believe that would come out to $O\big(\frac{x^{2/3}}{\log{n}}\big)$ for the nth prime. In practice typically one does a good approximation, a single call for the fast prime count, followed by sieving the remainder as this is typically an extremely small range and usually faster than a second prime count, much less $\log n$ of them.

As to your question of whether this can be done directly, the last paragraph gives a well-defined algorithm, so yes, but it isn't a closed form function. Calculating the nth prime by sieving to n works fine for small inputs, but is massively slower for large inputs. Even at just $10^{10}$, primesieve is about 2000x slower than the inverse fast prime count method, and the gap keeps widening.

$\endgroup$
  • $\begingroup$ LMO = Lagarias, Miller, Odlyzko if you want to look it up. $\endgroup$ – gnasher729 Nov 20 '16 at 13:08

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.