I am doing Project Euler Problem 3, but I seem to get stuck. I have written some code that makes sense (at least to me) but keeps printing the answer to 137.
This is the problem:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
using namespace std;
int number = sqrt(600851475143);
int biggestprime = calcprime(number);
cout << "The biggest prime is: " << biggestprime << endl;
bool isprime(int number)
for (int i = 2; i <= sqrt(number); i++)
if (number % i == 0)
int calcprime(int number)
for (int i = number; i > 2; i--)
if ((number % i == 0) && (isprime(i)))
I know that the long long type works for the number, but when I change all my ints to long long's, it never finishes running (don't really know why, maybe it's taking too long). So I took the sqrt of the number instead because that would be the biggest number divisible by that large number (besides the large number itself).
Not sure why this program always ends up with 137, though.
This is just a guess, but I think you may have a logic error in that if you are looking for the largest prime factor you should do the upper half of the possible factors. You are decrementing from sqrt(bignum) to 2. You should be decrementing from bignum to sqrt(bignum).