Hello I am trying to solve the ProjectEuler #3, the largest prime factor problem, here is the specification:The prime factors of 13195 are 5, 7, 13 and 29.What is the largest prime factor of the number 600851475143 ?Here is my code in C++:#include <iostream>#include <math.h>bool isPrime(int num) {    if (num <= 3) {        return num > 1;    } else if (num % 2 == 0 || num % 3 == 0) {        return false;    } else {        for (int i = 5; i * i <= num; i += 6) {            if (num % i == 0 || num % (i + 2) == 0) {                return false;            }        }        return true;    }}int main(int argc, char const *argv[]) {    long input = 13195;    long product = 2;    for (int m = 2; m < input; m++) {        if (input % m == 0) {            if (isPrime(m)) {                std::cout << m << std::endl;                product *= m;                if (product == input)                    break;            }        }    }    return 0;}Up to now I haven't done finding the largest one, I am just trying to list all of the prime factors.Here is my output:For 13195, the out put is OK, it returns the following numbers correctly:5 7 13 29However when I try to apply this to 600851475143, the output is correct too but it seems keeps calculating and return an error message eventually:71 839 1471 6857 Floating point exception: 8Thanks in advance if you can figure out where the problem is.
Largest prime factor - C++ version
c++
The numbers you are dealing with overflow the size of ints. Replace int with long and you will get no errors.However your algorithm is quite inefficient. You are looking for all divisors of your input and then check if the divisor is prime. But the smaller divisor of a number is always a prime... so no check is needed. Moreover once you find a divisor you can divide your input by it, so that you reduce the input. It is funny that you try to optimize the isPrime function (to get a code which is three time faster) when all the complexity is given by the main loop.The solution can be as simple as the following:#include <iostream>using namespace std;int main() {  long n = 600851475143;  for (long i=2; i*i < n; ++i) {    while (n % i == 0) {      cerr << Factor found:  << i << endl;      if (n>i) n /= i;    }  }  cout << Largest factor:  << n << endl;}