Problem 003 : Largest Prime Factor

Largest prime factor

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

                                                                                                           https://projecteuler.net/problem=3

Problem 3 is about prime factorization.

Before we get into the problem, let's talk briefly about prime numbers and factorization.

(I will talk about prime numbers and primality more specifically in later problems.)

Here are some properties that we need to know:

1. Except for 2, all prime numbers are odd numbers.

2. When we divide a number, there is always a pair of divisors except for perfect squares.

    For example, if we look at divisors of 12 : 1, 2, 3, 4, 6, 12

    we can easily find three pairs (1, 12), (2, 6), (3, 4)

    and each pair will have a product of original number (which is 12 in this case).

    So we can conclude that if 12 is divisible by 1, then it is divisible by 12 for sure.

                                            if 12 is divisible by 2, then it is divisible by 6 for sure.

                                            if 12 is divisible by 3, then it is divisible by 4 for sure.

    We now divide them into two groups: smaller group (1, 2, 3) and larger group (4, 6, 12).

    And we see that the dividing borderline is between 3 and 4.

    This dividing borderline can be calculated by taking square root of 12, which is 3.4641

    Therefore, when we want to test divisibility, we just need to test divisors up to the square root of
    the original number, and we can raise efficiency by removing redundancy of calculation.

    One exception is when we have a perfect square, because the square root of perfect square is an

    integer, which cannot be a clear dividing borderline of divisors.

    For example, if we look at the divisors of 16: 1, 2, 4, 8, 16

    We get an odd number of divisors. Also, 4 can be either smaller or larger group.

    This is the reason that when we make an universal solutions for finding factors, we need to include
    square root of the number: from i = 2 up to i <= sqrt (original number)

In this problem, our number is 600851475143, which is neither an even number nor a perfect square.

Because it is not an even number, we don't need to divide it by 2. As stated above, all prime numbers other than 2 are odd, and we just need to test odd divisors; starting with i = 3, we can increment by 2 so that we can test just odd numbers (3, 5, 7, ...).

If we continue dividing a number by 3 (if it is divisible by 3) until it cannot be divided further, then the remnant is not multiple of 3 anymore. Do the same process for 5 and 7. When we reach divisor 9, it is not a prime factor since 9 is not a prime number. But we don't need to worry about it since we got rid of all the 3's from the number in earlier step. This is how we can do prime factorization without explicitly checking if the divisor itself is a prime number.

When we reach to the point where the number cannot be divided by any divisors smaller than its square root, then that remaining number would be the last number of our prime factorization, which is the answer to the problem.

public static void run()
{
    long d = 600851475143L;
 
    for (int i = 3; i < Math.sqrt(d); i+=2)
    {
         if (d%i == 0)
             while (d%i == 0) d /= i;
    }
    System.out.println(d);
}

Answer is 6857

Execution time is 2 ms, or 0.002 seconds

Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem003.java

I also made a universal solution for finding largest prime factor of a number in source code, so if you need any help about that, feel free to leave comment and ask questions.

public static int getLargestPrimeFactor(int n)
{

    if (n == 1) return 1; 
    if (n%2 == 0) while (n%2 == 0) n /= 2;
    if (n == 1) return 2;
  
    int i = 3;
    for ( ; i <= (int)Math.sqrt(n); i+=2)
    {
        if (n%i == 0)
             while (n%i == 0) n /= i;
    }
    i -= 2;
    if (n == 1) return i;
    return n;
}