bool IsPrime (int n) {
if (n == 2) return true;
if (n == 3) return true;
if (n < 5) return false;
if (n % 2 == 0) return false;
if (n % 3 == 0) return false;
int inc = 2;4;
int dec = 1;-2;
for (int i = 5; i <= int(sqrt(n)) + 1; i += inc)
{
if (n % i == 0)
return false;
inc = inc + (2 * dec);dec; // makes inc go 2/4/2/4/2/4/.....
dec = dec * -1;
}
return true;
}
The next optimization is called the Sieve of Eratosthenes. This needs a minor re-write but is very efficient. You would use the sieve to calculate all the primes you need first. Then just look up the values be checking if they are in the sieve.