<p>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).</p>

<p><a href="http://en.wikipedia.org/wiki/Prime_gap" rel="nofollow">http://en.wikipedia.org/wiki/Prime_gap</a></p>

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

CC BY-SA 3.0
2013-02-16T00:42:40.107Z
QiCheng how do you achieve $n^{0.525}$?
usul
CC BY-SA 3.0
2013-02-16T01:51:53.303Z
$n^{0.525}$ is polynomial in $n$, but this is exponential in the size of the input, which is $\log n$.
a06e
CC BY-SA 3.0
2013-02-16T05:02:49.273Z
Well, it is known that between $n$ and $n + n^{0.525}$ there must be a prime
QiCheng
CC BY-SA 3.0
2013-02-16T13:55:35.277Z
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
CC BY-SA 3.0
2013-02-16T15:24:08.327Z
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}.
QiCheng
CC BY-SA 3.0
2013-02-15T23:25:55.303Z
2013-02-16T16:09:21.270Z
2013-02-16T16:09:21.270Z
QiCheng
<p>What's the best known complexity for the following problem? Given a number $n$, return the smallest prime larger than $n$. </p>

<p>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. </p>

CC BY-SA 3.0
2013-02-15T21:54:40.323Z
possible duplicate of [Finding a prime greater than a given bound](http://cstheory.stackexchange.com/questions/4882/finding-a-prime-greater-than-a-given-bound)
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-15T21:57:35.920Z
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
CC BY-SA 3.0
2013-02-15T22:14:42.350Z
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
<cc.complexity-theory>
Find next prime
user13768
# Find next prime

(Asked by: username_0 on 2013-02-15)

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.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: possible duplicate of [Finding a prime greater than a given bound](http://cstheory.stackexchange.com/questions/4882/finding-a-prime-greater-than-a-given-bound)  
> **username_0**: 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$.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2013-02-15. Score: 7

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

> **Comments:**
> **username_3**: QiCheng how do you achieve $n^{0.525}$?  
> **username_4**: $n^{0.525}$ is polynomial in $n$, but this is exponential in the size of the input, which is $\log n$.  
> **username_2**: Well, it is known that between $n$ and $n + n^{0.525}$ there must be a prime  
> **username_3**: 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?  
> **username_2**: 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}.  

---

