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. It's a good answer but not the biggest. But if I change i = 1471 it gives me the correct answer 6857 ... Where is the problem? Why doesn't it "automagically" give me the good 6857 answer but 1471 when I start from 2?

PS. I know I don't have to use long long everywhere.

Answer 1

Your factorization algorithm needs to pick between C and A, because at the end of the process A contains the remainder, which is also a factor of the original A. If it happens to be the largest one, your code would miss it.

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

Once you make this modification, your code produces the correct answer (demo).

Note: now that your program is running, you may consider a few modifications:

• Trying out potential divisors until you reach A/2 is inefficient; you can stop at the square root (do you see why?)
• Checking for primality is not required in the way that you have structured your program
• Checking for primality by trying out all numbers, i.e. the way the math definition goes, is grossly inefficient: you are trying out too many divisors that are guaranteed to not work. Again, you can stop at the square root. If you start at 2, not at 1, stop at the square root, and find no divisors, the number is prime.