What is wrong with this code for Project Euler # 3?

Question

#include <iostream> using namespace std; int prim( long long x ) { int s = 0; for( long long i = 1; i <= x ; i++ ) { if( x % i == 0 ) { s++; } } if( s == 2 ) { return 1; } return 0; } 

---

 int main() { long long A = 600851475143; long long i = 2; long long C = 0; while( i < (A/2) ) { while( A % i == 0 ) { A = A / i; if( i > C ) { C = i; } } i++; } if( prim(C) ) { cout<<C; } return 0; } 

This is the code I made for Project Euler problem 3 . I don’t understand why, when I run it, it gives me 1471. This is a good answer, but not the biggest one. But if I change i = 1471 , it will give the correct answer 6857 ... Where is the problem? Why doesn't this “automatically” give me a good answer 6868, but 1471 when I start with 2?

PS. I know that I do not need to use long long everywhere.

Answer 1

Your factorization algorithm should choose between C and A , because at the end of process A is a remainder that is also a factor of the original A If it is the largest, your code will skip it.

 if (A > C) { C = A; } 

After making this modification, your code will give the correct answer ( demo ).

Note. Now that your program is running, you can consider a few changes:

• Trying to split up potential dividers until you reach A/2 is ineffective; you can stop at the square root (you see why?)
• Validation is not required in the way you structure your program.
• Testing for simplicity by testing all numbers, that is, a way to determine math, is extremely inefficient: you try too many divisors that are guaranteed to not work. Again, you can stop at the square root. If you start with 2, not 1, stop at the square root and find no divisors, the number will be prime.