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 <iostream>
#include <math.h>
using namespace std;
bool IsPrime (int n) {
if (n < 2) return false;
if (n < 4) return true;
if (n % 2 == 0) return false;
for (int i = 3; i <= int(sqrt(n)) + 1; i += 2)
if (n % i == 0)
return false;
return true;
}
int main () {
long long x;
int lpf = 0; //Largest Prime Factor
cin >> x;
for (int n = 0; n <= x; n++)
if (IsPrime(n) && x % n == 0)
lpf = n;
cout << lpf;
}