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\n", 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!

Answer 2

I suggest you to improve the primality check part of your code. The running time of your method is O(n²) so you should use a more efficient algorithm for this like the well-known Miller–Rabin primality test with O(klog³n). I provide a pseudo code here for you and you can write the code on your own:

Input: n > 3, an odd integer to be tested for primality;
Input: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
   pick a random integer a in the range [2, n − 2]
   x ← ad mod n
   if x = 1 or x = n − 1 then do next WitnessLoop
   repeat s − 1 times:
      x ← x2 mod n
      if x = 1 then return composite
      if x = n − 1 then do next WitnessLoop
   return composite
return probably prime

---

I provide a link for you to see an implementation in python that also compares this algorithm with yours. BTW, there are many implementations of this algorithm all over the web but I think righting it by yourself may help you to better understand it.

Answer 3

Try the following code. It essentially implements the points in the accepted answer. The only improvement is that it skips all multiples of 2, 3, and 5 using wheel factorization http://en.wikipedia.org/wiki/Wheel_factorization

//find largest prime factor for x <2^64
#include <stdio.h>
#include <stdint.h>
int main() {
    uint64_t x = 600851475143;
    int wheel[] = {4,2,4,2,4,6,2,6};
    while(x>2 && x%2==0) x/=2;
    while(x>3 && x%3==0) x/=3;
    while(x>5 && x%5==0) x/=5;   
    for(uint64_t j=0, i=7; i<=x/i; i+=wheel[j++], j%=8) {
        while(x>i && x%i==0) x/=i;
    }
    printf("%llu\n", x);
}

Another thing that could be done is to pre-compute all primes less than 2^32 (rather than downloading them) and then only divide by the primes. The fastest method I know to do this is the Sieve of Eratosthenes. Here is a version using OpenMP which finds the primes up to 1 billion in less than one second http://create.stephan-brumme.com/eratosthenes/