Project Euler #3 - Java

Question:

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

What is the largest prime factor of the number 600851475143 ?

Solution:

We are going to assume that a list of prime numbers is NOT available to solve this problem. Still, this question is simple as long as you know one basic law of mathematics: all composite numbers can be written as a product of primes. I'm going to omit the proof (by contradiction) and ask you to just trust me on this. For example,

8 = 2*2*2 

9 = 3*3 

10 = 2*5 

147 = 3*7*7

So now with that little nugget tucked away we can tackle this problem. The solution is to loop through 2 and every odd integer and check whether the integer divides evenly into our subject number. If it does, divide the subject by that integer repeatedly until a remainder is found. Once a remainder is found, continue on to the next integer. Finally, we stop looking for a new integer when our subject equals 1. 

You might be thinking, "wait, does that really work?" I assure you, it does. Let's look at our previous examples.

Subject: 8

Integer: 2

Iteration 1: Does 2 divide 8? Yes, so divide 8 by 2.

Iteration 2: Does 2 divide 4? Yes, so divide 4 by 2. 

Iteration 3: Does 2 divide 2? Yes, so divide by 2. 

Iteration 4: Does 2 divide 1? Nope!... subject equals 1. 

Highest prime that divides 8 is 2.  

   

Subject: 147

Integer: 2

Iteration 1: Does 2 divide 147? No, increase Integer. 

Iteration 2: Does 3 divide 147? Yes, so divide by 3. 

Iteration 3: Does 3 divide 49? No, increase Integer.

Iteration 5: Does 5 divide 49? No, increase Integer. 

Iteration 7: Does 7 divide 49? Yes, so divide by 7. 

Iteration 8: Does 7 divide 7? Yes, so divide by 7.

Iteration 9: Does 7 divide 1? No. Subject equals 1. 

Highest prime that divides 147 is 7. 

This algorithm works for ALL numbers. So without further adieu, my solution. With all this in mind, I do not believe my code needs any further explanation.

import java.math.BigInteger;


public class euler_03
{
    public static void main(String[] args)
    {
        BigInteger dividend = new BigInteger("600851475143");
        BigInteger divisor = new BigInteger("3"); // Skip 2 since this is an odd number
        int high = 3;
       
        while(true)
        {
            // Continually divide until no remainder
            while (dividend.remainder(divisor).equals(BigInteger.ZERO))
            {
                dividend = dividend.divide(divisor);
                high = divisor.intValue();
            }
           
            divisor = divisor.add(BigInteger.valueOf(2));
           
            if (dividend.equals(BigInteger.ONE))
                break;
        }
       
        System.out.printf("The highest prime factor is %d\n", high);
    }
}