Finding a prime number after a given number

Question

How can I find the least prime number greater than a given number? For example, given 4, I need 5; given 7, I need 11.

I would like to know some ideas on best algorithms to do this. One method that I thought of was generate primes numbers through the Sieve of Eratosthenes, and then find the prime after the given number.

Answer 1

Source: Wikipedia

Bertrand's postulate (actually a theorem) states that if n > 3 is an integer, then there always exists at least one prime number p with n < p < 2n − 2. A weaker but more elegant formulation is: for every n > 1 there is always at least one prime p such that n < p < 2n.

So if I am given a number, say n, than I can check in the range (n, 2*n) [open interval excluding n and 2*n]

int GetNextPrime(int n) {     bool isPrime = false;     for (int i = n; i < 2 * n; ++i)     {     // go with your regular prime checking routine     // as soon as you find a prime, break this for loop     } } 

Answer 2

Some other methods have been suggested and I think that they are good, but it really depends on how much you want to have to store or compute on the spot. For instance if you are looking for the next prime after a very large number, then using the Sieve of Eratosthenes might not be so great because of the number of bits you would need to store.

Alternatively, you could check all odd integers between (and including) 3 and sqrt(N) on every number odd number N greater than the input number until you find the correct number. Of course you can stop checking when you find it is composite.

If you want a different method, then I would suggest using the Miller-Rabin primality test on all odd numbers above the input number (assuming the input is > 1) until a prime is found. If you follow the list, located at the bottom of the page, of numbers a to check for the given ranges, you can significantly cut down on the number of as you need to check. Of course, you might want to check at least a few of the smaller primes (3,5,7,11 for instance) before checking with Miller-Rabin.