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).

Answer 2

It's probably a 32-bit system. The number 600851475143 is bigger than 32 bits.

Instead of long i try:

long long i;

And instead of printf("%d\n", i); try:

printf("%lld\n", i);

And use 600851475143LL in place of 600851475143.

Answer 3

You can start your loop with the greatest integer less than or equal to the square root of your large number. Then you can find factor pairs working down through the loop. Write a separate function to check whether a given number is prime. If the larger factor of the pair is prime, return it. If the larger is not prime, check if the smaller is prime and if so return it.