Search code examples
algorithmprimes

Next prime number algorithm

i want to know if there is a easy way to find the prime number next to X.

For example, if X=2, the next prime will be 3. The algorithm that i have would be ok, if i wanted to know little numbers but i want to calculate like X=3 million.

I found a algorithm to calculate primes, but it takes a lot of time to calculate them, since it calculates all primes from 0 to X... For example for 1 million, it takes almost 2 minutes.

Question is... How can i find the next prime number? Is there an efficient algorithm? Best solution i found is to check if X+1 is prime and increase until one is found...

Solution

  • One possible solution is instead of increasing the number by one, you can increment the number by two if the number is odd else increment by one and then in all future iterations increment by two.

    Like in the below code snippet

    if (num is odd)
    check_prime_of(num+2);
else /*num is even and not equal to 2*/
    check_prime_of(num+1);