Java - Can't make ProjectEuler 3 Work for a very big number (600851475143)

Question

Resolution:
It turns out there is (probably) "nothing wrong" with the code itself; it is just inefficient. If my math is correct, If I leave it running it will be done by Friday, October 14, 2011. I'll let you know!

Warning: this may contain spoilers if you are trying to solve Project Euler #3.

The problem says this:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Here's my attempt to solve it. I'm just starting with Java and programming in general, and I know this isn't the nicest or most efficient solution.

import java.util.ArrayList;

public class Improved {
    public static void main(String[] args) {
        long number = 600851475143L;
        // long number = 13195L;
        long check = number - 1;
        boolean prime = true;

        ArrayList<Number> allPrimes = new ArrayList<Number>();

        do {
            for (long i = check - 1; i > 2; i--) {
                if (check % i == 0) {
                    prime = false;
                }
            }

            if (prime == true && number % check == 0) {
                allPrimes.add(check);
            }

            prime = true;
            check--;
        } while (check > 2);

        System.out.println(allPrimes);
    }
}

When number is set to 13195, the program works just fine, producing the result [29, 13, 7, 5] as it should.

Why doesn't this work for larger values of number?

---

Closely related (but not dupe): "Integer number too large" error message for 600851475143

Answer 1

The code is very slow; it is probably correct but will run for an unacceptably large amount of time (about n^2/2 iterations of the innermost loop for an input n). Try computing the factors from smallest to largest, and divide out each factor as you find it, such as:

for (i = 2; i*i <= n; ++i) {
  if (n % i == 0) {
    allPrimes.add(i);
    while (n % i == 0) n /= i;
  }
}
if (n != 1) allPrimes.add(n);

Note that this code will only add prime factors, even without an explicit check for primality.

Answer 2

You could also speed this up by only checking from 2 to the square root of the target number. Each factor comes in a pair, one above the square root and one below, so when you find one factor you also find it's pair. In the case of the prime test, once you find any factor you can break out of the loop.

Another optimization could be to find the factors before checking that they are prime.

And for very large numbers, it really is faster to experiment with a sieve rather than brute forcing it, especially if you are testing a lot of numbers for primes. Just be careful you're not doing something algorithmically inefficient to implement the sieve (for example, adding or removing primes from lists will cost you an extra O(n)).

Answer 3

Almost all the Project Euler problems can be solved using a signed datatype with 64 bits (with the exception of problems that purposefully try to go big like problem 13).

If your going to be working with primes (hey, its project Euler, your going to be working with primes) get a headstart and implement the Sieve of Eratosthenes, Sieve of Atkin, or Sieve of Sundaram.

One mathematical trick used across many problems is short circuiting finding factors by working to the square root of the target. Anything greater than the square corresponds to a factor less than the square.

Answer 4

Another approach (there is no need to store all primes):

private static boolean isOddPrime(long x) {
    /* because x is odd, the even factors can be skipped */
    for ( int i = 3 ; i*i <= x ; i+=2 ) {
        if ( x % i == 0 ) {
            return false;
        }               
    }
    return true;
}

public static void main(String[] args) {
    long nr = 600851475143L;
    long max = 1;
    for ( long i = 3; i <= nr ; i+=2 ) {
        if ( nr % i == 0 ) {
            nr/=i;
            if ( isOddPrime(i) ){
                max = i;
            }
        }   
    }
    System.out.println(max);
}

It takes less than 1 ms.