Project Euler #3 - Solution runs forever

Question

First time I've ever encountered this problem. It feels like it will never end.

My approach:

import java.util.TreeSet;

public class Euler3 {
    public static void main(String[] args) {
        long result = 0;
        long startTime = System.nanoTime();

        long numberGiven = 600851475143L;
        TreeSet<Long> nums = new TreeSet<>();

        for (long i = 2L; i < numberGiven; i++) {
            if (numberGiven % i == 0 && isPrime(i)) {
                nums.add(i);
            }
        }

        result = nums.last();   

        System.out.print("Result: " + result +
            ".\nTime used for calculation in nanoseconds: " +
            (System.nanoTime() - startTime) + ".");
    }

    public static boolean isPrime(long n) {
        if (n <= 3) {
            return n == 1 ? false : true;
        } else if (n % 2 == 0 || n % 3 == 0) {
            return false;
        } else {
            for (int i = 5; i * i <= n; i += 6) {
                if (n % i == 0 || n % (i + 2) == 0) {
                    return false;
                }
            }
        return true;
        }
    }
}

Of course this works on smaller numbers, but as is probably intended doesn't seem effective on over 600 billion. I'm wondering, without giving the answer away:

1. Is there some obvious alteration I could employ to reduce the running time/checks necessary?

2. Although it clearly doesn't work effectively here, is this approach otherwise acceptable or would someone who posted this challenge, even with a smaller number, be looking for something different?

3. I tried with integers the first time and got an overflow related error, is anything similar happening under the hood that would actually prevent this from terminating?

Answer 1

For every number you're checking that's a factor, you're doing an internal loop to figure out if it's a prime. That means your algorithm is effectively performing n * m operations.

You can instead use the following mathematical "trick", which I think is the same used by the UNIX factor program.

Since every number over one is either prime or a unique product of a set of primes (with potential duplicates in the set), we can just start dividing the number by the first prime two (actually reducing the number in the process) until that's no longer possible (i.e., it becomes odd). At that point, the reduced number will not have two or any multiples of two as a factor.

Then we do the same by continuously dividing by three until that's no longer possible.

Now you'd think that may be onerous but, because you've stripped out all the 'two' factors, the number cannot possibly be a multiple of four (or any other even number for that matter). So we detect that and move up to the next divisor of five and start dividing by that.

So the division operation are only done for prime divisors, speeding things up considerably. In addition, once the divisor gets above the square root of the (reduced) number, no more factors are possible, so we exit. In that case, the reduced number gives us the final (hence highest) prime factor.

For example, consider the number 924:

Number  Divisor  Result
------  -------  ------
   924        2*    462
   462        2*    231
   231        2     not divisible, go to 3
   231        3*     77
    77        3     not divisible, go to 4
    77        4     not divisible, go to 5
    77        5     not divisible, go to 6
    77        6     not divisible, go to 7
    77        7*    11
    11*       7     stop since 7 * 7 > 11

So the prime factors of 924 are {2, 2, 3, 7, 11}.

---

Now I urge you to try that algorithm on your own before looking below since the entire point of Euler is to test your own abilities. I simply provide the solution for completeness:

public class Test
{
    public static void main(String[] args) {
        long startTime = System.nanoTime();

        long number = 600851475143L;

        // Start with a divisor of two,
        // continue until over sqrt(number).

        long divisor = 2L;
        while (divisor * divisor <= number) {
            if ((number % divisor) == 0) {
                // If factor, output then reduce number.

                System.out.println(divisor);
                number = number / divisor;
            } else {
                // Otherwise, move to next divisor.

                divisor++;
            }
        }

        // Final number is final divisor.

        System.out.println(number);

        System.out.print("Time used for calculation in nanoseconds: " +
                (System.nanoTime() - startTime) + ".");
    }
}

That gives you the four prime factors in about five thousandths of a second (on my box, anyway):

71
839
1471
6857
Time used for calculation in nanoseconds: 458826.

Answer 2

The program can be simple like this, which runs under a second:

long val = 600851475143L;
long ans = 0;
for(long i = 2; i*i <= val; i++){
    if(val % i == 0){
       ans = i;
       while(val % i == 0)//This step will make sure that i is prime
           val /= i;
    }
}
if(val != 1){//If val is not 1, so val is a prime
   ans = val > ans ? val : ans;
}
System.out.println(ans);

Answer is 6857, and it is correct answer :)

Notice that we only check for all i values which i*i smaller than val.