In this blog post we will be looking at problem 3 of Project Euler and we will be doing it in Java.

This problem of project Euler found here, Below is the problem for quick lookup.

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

What is the largest prime factor of the number 600851475143 ?

-Project Euler problem 3

Prime numbers are numbers only dividable by itself or 1 without any remainder. A factor is simply one of the numbers used in multiplication, so if we were to have this sum: 8*4=32 then 8 and 4 are the factors.

Special case for two

We know that except for 2 all prime numbers are odd. If we make a special case for 2 we should only consider odd numbers after that. Saving 50% on execution time.

We start with the special case for 2, We continue dividing by 2 as long as the number is even, maybe we have multiple factors all being 2. (Ex 8 is actually three times 2 as a prime factor, 2x2x2=8)

long number = 600851475143L;
while (number % 2 == 0) {
    System.out.println(2);
    number = number / 2;
}

Considering all uneven numbers above two

We can figure out factors by dividing the long input number by the number we are considering as a prime factor(variable i), but we should only do this if there is no remainder. We save the new factor in the number variable to continue considering factors with it.

If we were to use 26 as the long input number the first factor would be 2 which gets figured out in the first code block. We then continue onto the code block below with 13 as variable number(since 13 is uneven we break out of the special case for 2 loop). In the for loop below we start variable i at 3, and continue considering uneven numbers(we increment by 2) till we find a number which divides 13 without a remainder. We do this loop as long as variable i is smaller or equal to the square root of the number.

for (int i = 3; i <= Math.sqrt(number); i += 2) {
    while (number % i == 0) {
        System.out.println(i);
        number = number / i;
    }
}

The code considers 3 -> 5 -> 7 -> 9 -> 11 -> 13 in that order. Breaking after 13 where number gets divided by variable i.

Since 13 is not dividable without a remainder by 3/5/7/9/11 nothing happens for those values and we increment variable i by 2 every time. When we get to 13 we can divide without a remainder giving us all the prime factors. and saving the new factor(in this case 1) in the number variable.

if the remaining number is higher than 1 it is also a prime factor so we print it.(Technically 1 too since every number without a remainder is evenly dividable by 1)

if (number > 1){ // One prime factor left! print it.
    System.out.println(number);
}

This gives us all the factors of the long number from small to big in the console output.

The output is:

71
839
1471
6857

The answer is 6857, it being the highest prime factor.

Check out the ‘Project Euler in Java’ page for more solutions!

Link to github.

That was Project Euler problem 3 in Java!