c - advice on how to make my algorithm faster

Question

here is my code in C for problem#3 from project-Euler, where I have to find the largest prime factor of 600851475143.

#include <stdio.h>
#include <stdlib.h>

bool is_prime(long int number){
     long int j;
     for (j=2; j<=number/2; j++){
             if (number%j==0) return false;
             if (j==number/2) return true;
            }
    }

int main(){

     long int input;
     scanf("%d", &input);
     long int factor;
     int ans=0;

     for (factor=input/2; factor>1; factor--){
             if (input%factor==0 && is_prime(factor)) {
                     ans = factor;
                     break;
                    }
            }

     printf("%d
", ans);
     system("pause");
     return 0;
    }

Although it works fine for small numbers, gradually it takes more and more time for it to give an answer. And, finally, for 600851475143 the code returns 0, which is obviously wrong. Could anyone help? thanks a lot.

Answer 1

A few things to consider:

1. As @Alex Reynolds pointed out, the number you're trying to factor might be so large that it can't fit in an int. You may need to use a long or a uint64_t to store the number. That alone might solve the problem.

2. Rather than checking each divisor and seeing which ones are prime, you might instead want to try this approach: set n to 600851475143. For each integer from 2 upward, try dividing n by that integer. If it cleanly divides out, then divide out all copies of that number from n and record the largest prime factor as being the current integer. If you think about it a bit, you'll notice that the only divisors you'll consider this way are prime numbers. As a helpful hint - if n has no divisors (other than 1) less than √n, then it's prime. That might help give you an upper bound on your search space that's much tighter than the division by two trick you're using.

3. Rather than increasing the divisor by one, try testing out 2 as a divisor and then only dividing by odd numbers (3, 5, 7, 9, 11, etc.) No even number other than 2 is prime, so this halves the number of numbers you need to divide by.

Alternatively, create a file storing all prime numbers up to √600851475143 by downloading a list of primes from the internet, then just test each one to see if any of them divide 600851475143 and take the biggest. :-)

Hope this helps!