Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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

1 Answer 1

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

share|improve this answer
    
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
2  
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
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}. –  QiCheng Feb 16 '13 at 15:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.