4
$\begingroup$

What's the best known complexity for the following problem? Given a number $n$, return the smallest prime larger than $n$.

Clearly one can just test all the odd numbers large than $n$ in turn until you find one. You can use a probabilistic primality testing algorithm with one-sided error and then confirm any primes using a AKS if needs be. This is slow but uses small space. Alternatively one could us a sieve which will be faster but uses potentially very large space.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ possible duplicate of Finding a prime greater than a given bound $\endgroup$
    – Tsuyoshi Ito
    Feb 15, 2013 at 21:54
  • $\begingroup$ The linked question seems to insist the algorithm is deterministic and also answers a different question. I am looking for the next prime, not any prime greater than $n$. $\endgroup$
    – user13768
    Feb 15, 2013 at 21:57
  • $\begingroup$ I thought that you were looking for a deterministic algorithm, but I was wrong, as was apparent from your example. I agree that it is a different question from the linked one; at least I do not know how to reduce one to the other in either direction. My apologies. $\endgroup$
    – Tsuyoshi Ito
    Feb 15, 2013 at 22:14

1 Answer 1

Reset to default
7
$\begingroup$

Heuristically there is a prime between $n$ and $n + log^2 n$ for any sufficiently large $n$, so yes there is a deterministic polynomial time algorithm, which works quite well in practice (but is heuristic).

http://en.wikipedia.org/wiki/Prime_gap

I do not think that there is a known algorithm with provable polynomial time algorithm for this problem. The best provable complexity you can achieve is $ n^{0.525} $.

Improve this answer
$\endgroup$
5
  • $\begingroup$ QiCheng how do you achieve $n^{0.525}$? $\endgroup$
    – usul
    Feb 16, 2013 at 0:42
  • $\begingroup$ $n^{0.525}$ is polynomial in $n$, but this is exponential in the size of the input, which is $\log n$. $\endgroup$
    – a06e
    Feb 16, 2013 at 1:51
  • 2
    $\begingroup$ Well, it is known that between $n$ and $n + n^{0.525}$ there must be a prime $\endgroup$
    – QiCheng
    Feb 16, 2013 at 5:02
  • $\begingroup$ OK, but if we include lower-order stuff, more specifically with AKS this gives about $n^{0.525} \log^6 n$; that is, $b^6 2^{0.525b}$ on $b$-bit input. Unless there is an asymptotic improvement in which numbers you check? $\endgroup$
    – usul
    Feb 16, 2013 at 13:55
  • 2
    $\begingroup$ In computational number theory, it is convention to use \tilde{O} for complexity. The "\log^6 n" disappear if you use \tilde{O}. In fact, the AKS time complexity of \log^6 n is also for \tilde{O}. $\endgroup$
    – QiCheng
    Feb 16, 2013 at 15:24

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.