Find next prime number algorithm

Question

I am looking forward to improve my algorithm to find the next primenumber to the right to a given number. What I have so far is this:

int NextPrime(int a)
{
    int i, j, count, num;
    for (i = a + 1; 1; i++)
    {
        for (j = 2, count = 0; j <= i; j++)
        {
            if (i%j == 0)
            {
                count++;
            }
        }
        if (count == 1)
        {
            return i;
            break;
        }
    }
}

Tho this algorithm is not that efficent when running often. Can someone give advices on how the algorithm could be speed up or improved.

The two basic speed ups are to increment j by 2 (starting from 3, after testing for 2) as only odd numbers other than 2 are prime. In addition, only checking up to the square root of the number (as one of the factors of any number is <= the square root.) — borrible, May 05 '15 at 11:59
see also [this related question](http://stackoverflow.com/q/453793/2994596) — SleuthEye, May 05 '15 at 12:02
I don't understand why people are downvoting every question. This is just hilarious. The sieve of Eratosthenes is not the right way here. — Dark Side, May 05 '15 at 14:15
Did you try to do some probabilistic primality tests before start of the inner cycle? http://en.wikipedia.org/wiki/Primality_test — Aleksei Shestakov, May 05 '15 at 14:33

Zoran Horvat · Accepted Answer · 2015-05-06T13:15:04.663

15

Sieve of Eratosthenes is not the best solution when only one prime number should be found. Here is the solution which is useful for that purpose. It is based on the idea that all prime numbers are in form of 6k+-1, so I'm only testing 2, 3 and numbers in form 6+-1. Of course, the loop quits when divisor breaches sqrt(a) because all such numbers have already been tested.

bool IsPrime(int number)
{

    if (number == 2 || number == 3)
        return true;

    if (number % 2 == 0 || number % 3 == 0)
        return false;

    int divisor = 6;
    while (divisor * divisor - 2 * divisor + 1 <= number)
    {

        if (number % (divisor - 1) == 0)
            return false;

        if (number % (divisor + 1) == 0)
            return false;

        divisor += 6;

    }

    return true;

}

int NextPrime(int a)
{

    while (!IsPrime(++a)) 
    { }
    return a;

}

Net result is that this loop works very fast on a couple of large numbers I've tried.

edited May 06 '15 at 13:15

answered May 05 '15 at 12:05

Zoran Horvat

10,924
3
31
43

3

Function `IsPrime` does not always work properly, for example the result for number `64144081 = 8009 ^ 2` is `true`. – Aleksei Shestakov May 05 '15 at 15:54
1

Hi @AlexeiShestakov, thank you for reporting this case. Actually, the stopping condition is wrong in my code - instead of running while divisor ^ 2 <= n, loop must continue while (divisor - 1) ^ 2 <= n. Great case of boundary condition bug, I will write this down! And you have a +1 from me. – Zoran Horvat May 06 '15 at 13:12
1

If you check for 2 in NextPrime before the while loop, you can do ++++a, adding 2 instead of 1, because 2 is the only even prime. – Sep 06 '15 at 23:46

score 3 · Answer 2 · answered May 05 '15 at 14:30

You can improve upon the sieve of Eratosthenes by a lot if you only check each number against each prime before it up until the square root of the prime number. For this you need to keep a list of all primes up to then. This increases memory cost but increases execution speed by a long shot.

Pseudocode:

List foundPrimes;
foundPrimes.add(1)
foundPrimes.add(2)

bool isPrime(int x) {
    for (int divisor in foundPrimes) {
        if (divisor*divisor > x) {
            foundPrimes.add(x);
            return true;
        } else if (x % divisor==0) {
            return false;
        }
    }
    // Invalid, need to run the algo from 3 on to fill the list
}

int nextPrime(int x) {
    while (!isPrime(++x)) {}
    return x;
}

Find next prime number algorithm

2 Answers2