Largest prime factor for a given number

I created a program to find the largest prime factor for a given number. The program works but unfortunately takes very long time to compute a huge number like 600851475143.

How can I optimise this program to run faster?

I don't know what does this multicore thing is, but I think it is a possible way to improve this program.

// A program to find the largest prime factor for a given number

#include 
#include 

using namespace std;

bool IsPrime (int n) {
   if (n > x;

    for (int n = 0; n <= x; n++) 
        if (IsPrime(n) && x % n == 0)
            lpf = n;

    cout << lpf;
}

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 = 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;
}

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   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;
}

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.

StackExchange Code Review Q#20180, answer score: 6