Project Euler 3: Largest prime factor

Question

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);

                }

            }   

        }

    }

}

Answer 1

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\$

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

2. 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.

3. 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);
    }
}

Answer 2

            //if i is a factor, check if its prime

It may be pedantic, but "its" should have an apostrophe in it if it is used as a contraction for "it is".

            // if i is a factor, check if it's prime

You are saying "check if it is prime".

More importantly, you don't need to check if the factors are prime if you do it right.

    public static void main(String[] args) {
        long num = 600851475143L;
        long i = 2;
        for ( ; i <= num; i++) {
            //if i is a factor, remove it
            while (num % i == 0) {
                num /= i;
            }
        }

        // the last number must be prime
        System.out.println(i-1);
    }

When this finds a factor, it removes it from num until the new num is no longer divisible by that factor. As a result, if num isn't prime, it's pretty fast. It is (mostly) linear in time relative to the answer.

Note that we can improve things by writing special cases for 2 and 3. Also, the worst behavior occurs when num is prime. If you check for that first, you can limit the worst case to \$O(\sqrt n)\$.

public class Euler3 {

    public long calculateLargestPrimeFactor(long number) {
        long current = 1;

        while (number % 2 == 0) {
            number /= 2;
            current = 2;
        }

        while (number % 3 == 0) {
            number /= 3;
            current = 3;
        }

        if (number == 1) {
            return current;
        }

        current = 5;
        int increment = 4;
        int sqrt_num = (int) Math.sqrt(number);
        for ( ; current <= number; current += increment) {
            if (current > sqrt_num) {
                return number;
            }

            // if current is a factor, remove it
            while (number % current == 0) {
                number /= current;
            }

            increment = 6 - increment;
        }

        // the last number must be prime
        return current - increment;
    }

    public static void main(String[] args) {
        System.out.println(calculateLargestPrimeFactor(600851475149L));
        System.out.println(calculateLargestPrimeFactor(600851475143L));
        System.out.println(calculateLargestPrimeFactor(2 * 600851475149L));
        System.out.println(calculateLargestPrimeFactor(20));
        System.out.println(calculateLargestPrimeFactor(22));
        System.out.println(calculateLargestPrimeFactor(1073741824));
        System.out.println(calculateLargestPrimeFactor(6561));
    }

}

Note that it would be more robust to do the main testing in JUnit or similar.

I also changed the name of i and num to current and number respectively to be clearer.

Answer 3

Performance

You can use a Sieve of Eratosthenes to make it faster.

This is a slightly more complicated sieve as it only sieves the odd numbers up to the square root of the input

public long largestPrimeFactor( final long input ) {
  // Initialise a BitSet for the sieve.
  final BitSet sieve = new BitSet( ((int) Math.sqrt( input )) + 1 );

  // Find if there are factors of 2 and eliminate them.
  long i = Long.numberOfTrailingZeros(input);
  long value      = input >> i;
  long maxPrime   = i > 0 ? 2 : 1;

  // Loop only over the values which remain in the sieve (i.e. the primes)
  for ( int j = 1; (i = (j<<1)+1) * i <= value; j = sieve.nextClearBit( j + 1 ) ){
    sieve.set(j);

    // Check if it is a factor
    if ( value % i == 0 )
    {
      maxPrime = i;
      // Eliminate the factor
      do value /= i; while( value % i == 0 );
      if ( value == 1 )
        break;
    }

    // Iterate through the sieve setting all the multiples
    // of the current value to be non-prime.
    for ( long k = (i*i-1)>>1; k * k <= value; k += i )
      sieve.set( (int) k);
  }

  return value > 1 ? value : maxPrime;
}

For small numbers, using a simple algorithm will be faster but if you (a) can re-use the sieve when finding/testing multiple numbers or (b) are using it for large numbers; then a sieve is likely to be faster.

Answer 4

Efficiency

1. Check only odd numbers
2. Check only numbers to the square root of the number under test
3. You maybe want to count down instead of count up

Robustness

1. You should have a look at BigInteger to avoid overflows and you think about numbers exceeding the Long-Type. This will not be easy.
2. You should not compare Integer-Values with Long-Values as you are using them within the same semantic. Harmonize the algorithm to use only one type for one purpose (in this case Long)

Naming

1. You have algorithms but no names. Break your algorithm in parts and name them meaningfully