Project Euler 3: Largest prime factor

How can I improve my code, make it more efficient, and are there any tips you have?

Project Euler 3:


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


What is the largest prime factor of the number 600851475143 ?

public class LargestPrimeFactor {

    public static void main(String[] args) {

        long num = 600851475143L;
        boolean isPrime = true;

        // this is to see if num is factorable
        for (int i = 2; i < num; i++) {

            //if i is a factor, check if its prime
            if (num % i == 0) {

                for (int j = 2; j < i; j++) {

                    if (i % j == 0) {

                        isPrime = false;

                    }

                }

                if (isPrime) {

                    System.out.println(i);

                }

            }   

        }

    }

}

A small note first, please do not double-space all lines in code, it just makes it harder to read, rather than easier.

Integer overflow

Using an int primitive type for i and j is causing the number to go through integer overflow and go back to its minimum value -2,147,483,648 (or \$-2^{31}\$), once it exceeds the maximum value 2,147,483,647 (or \$2^{31}-1\$), then finally all the way back from there to \$0\$, resulting in a java.lang.ArithmeticException: divide by zero. To correct this, use a long type for the iterators instead:

// this is to see if num is factorable
    for (long i = 2; i < num; i++) {
        //if i is a factor, check if its prime
        if (num % i == 0) {
            for (long j = 2; j < i; j++) {

Algorithm

With the above problem fixed, we can now see that the algorithm you use has a few problems. Given the number \$n = 600851475143\$

-
It checks every number \$i\$ in the set \$[2,3,4, \ldots, n-1]\$ to see if it is a factor of \$n\$.

-
For each \$i\$, it then checks every number \$j\$ in the set \$[i, i+1, i+2,\ldots, n-2]\$ to see if it is prime.

-
It returns each number that matches both criteria, e.g., 71, 839, 1471 and finally the answer, and then it just keeps on going until \$i = 600851475143 - 1\$, which takes a very long time.

The "right" algorithm is very simple, and involves no primality testing. I left an explanation of it in the code comments. This finds the right answer in less than 1 second. There would be other ways to improve it to be more Java/object-oriented, but for the sake of a math exercise like this it should do pretty nicely. Here is a live demo as well.

class LargestPrimeFactor  {

    public static void main(String[] args) {

        long N = 600851475143L;

        // First, start from the maximum number and divide by 2
        // until you can no longer divide evenly by 2, i.e., the number is odd
        while (N % 2 == 0) {

            // in the case of 600851475143 this will be skipped entirely since it is an odd number, 
            // but for the sake of generality we will keep it so it can be used on any number
            N /= 2;
        }

        // the next prime number is 3, and all prime numbers from there are odd numbers,
        // so we can safely just add 2 to the factor each time and only test for odd numbers
        // note that this has a small inefficiency in that it will also test for a few non-prime odd numbers
        // like 9, 15, 21, etc. but it's much less computational work to try dividing by a candidate factor than to test for primality.
        for (long factor = 3; factor < N; factor += 2) {

            // if N is evenly divisible by the factor, then we just divide it, and we keep going
            // until N can no longer be divided by a number smaller than itself,
            // in other words, until N is a prime number
            while (N % factor == 0 && factor < N) {
                N /= factor;
            }
        }
        System.out.println("The answer is " + N);
    }
}

StackExchange Code Review Q#133727, answer score: 11