# 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 Feb 15, 2013 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$. Feb 15, 2013 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. Feb 15, 2013 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).

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}$.

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