Skip to main content
added 298 characters in body
Source Link
Loki Astari
  • 97.7k
  • 5
  • 126
  • 341
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.

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;
   int dec = 1;
   for (int i = 5; i <= int(sqrt(n)) + 1; i += inc)
   {
       if (n % i == 0)
               return false;
       inc = inc + (2 * dec);  // makes inc go 2/4/2/4/2/4/.....
       dec = dec * -1;
   }
   return true;
}
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 = 4;
   int dec = -2;
   for (int i = 5; i <= int(sqrt(n)) + 1; i += inc)
   {
       if (n % i == 0)
               return false;
       inc = inc + 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.

Source Link
Loki Astari
  • 97.7k
  • 5
  • 126
  • 341

You have done the optimization of removing multiples of 2 (by incrementing by 2).

There is another slight improvement that removes multiples of 2 and 3 from the test.

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;
   int dec = 1;
   for (int i = 5; i <= int(sqrt(n)) + 1; i += inc)
   {
       if (n % i == 0)
               return false;
       inc = inc + (2 * dec);  // makes inc go 2/4/2/4/2/4/.....
       dec = dec * -1;
   }
   return true;
}

Another optimization for IsPrime() is that you only need to test using primes. ie no pointing in testing with 6 (its not prime) as all values that are divisible by 6 are also divisible by 3 (is prime). So if your loop only tested by using other primes:

// Assumes you are calling this function with monotimically inreassing
// values of n so that the `foundPrimes` vector will be constructed in order.
bool IsPrime (int n) {

   static std::vector<int>   foundPrimes = { 2, 3, 5, 7, 11 };

   for(std::size_t loop = 0; loop <  foundPrimes.size(); ++loop)
   {
       if (n == foundPrimes[loop])     { return true;}
       if (n % foundPrimes[loop] == 0) { return false;}
   }
   start = foundPrimes.last() + 2;

   for (int i = start; i <= int(sqrt(n)) + 1; i += 2)
   {
       if (n % i == 0)
               return false;
   }
   foundPrimes.push_back(n);
   return true;
}