# Find next prime

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.

• possible duplicate of Finding a prime greater than a given bound – Tsuyoshi Ito Feb 15 '13 at 21:54
• 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$. – user13768 Feb 15 '13 at 21:57
• 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. – Tsuyoshi Ito Feb 15 '13 at 22:14

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).
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}$.
• QiCheng how do you achieve $n^{0.525}$? – usul Feb 16 '13 at 0:42
• $n^{0.525}$ is polynomial in $n$, but this is exponential in the size of the input, which is $\log n$. – becko Feb 16 '13 at 1:51
• Well, it is known that between $n$ and $n + n^{0.525}$ there must be a prime – QiCheng Feb 16 '13 at 5:02
• 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? – usul Feb 16 '13 at 13:55