What's wrong with my C code? (Prime factors of a big number)

Question

Could you please help me?

I'm a beginner at C and my code doesn't work.

I'm trying to determine largest prime factor of 600851475143 and when I run the code, it just does nothing. Trying with smaller number however works.

long i;

for (i = 600851475143; i > 1; i--)
{
    if (600851475143 % i == 0)
    {
        printf("%d\n", i);
    }
};

Answer 1

First of all, the correct way to print a long is not %d but %ld (d = decimal, ld = long decimal). If long and int have different sizes on your system (which is not unusual), the results would not print correctly to begin with.

Next possible problem is that 600851475143 is more than fits into a 32 bit variable, yet long is only guaranteed to be at least 32 bit. It may be bigger than that, but only 32 bits are guaranteed. So are you sure that long is big enough on your system?

Try

printf("%zu\n", sizeof(long));

if it says 8, everything is fine, if it says only 4, long is not sufficient and you need to use long long instead (and %lld for printf, lld = long long decimal).

Last but not least, you are aware that your loop needs to do 600 billion iterations, aren't you? Even if you have a very fast system with a very fast CPU this will take quite some time to complete. So you will see 600851475143 printed to the screen immediately, but it will take quite some time before your code terminates (or finds another divisor, in case this is not a prime number).

Optionally: Instead of writing 600851475143, you may write 600851475143LL to let the compiler know you want this number to be of type long long. It seems like the C 2011 standard doesn't require this any longer (numbers are automatically treated as long or long long if required), yet I know that pior to C 2011 some compilers least issued a warning for numbers being bigger than int (or bigger than long).