Project Euler: #3 - Largest prime factor

Problem

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

What is the largest prime factor of the number 600851475143?

---

Problem Description

If any given number, N is divisible by x without leaving a reminder, then x is a Factor of the Number N.

Similarly, a Prime Number is a number that is divisible by 1 and itself. In other words, it has only 2 factors - 1 and itself.

Well, 10 is not a prime number as it has other factors like 2 and 5. And 2 is the only even prime number we have and all the other prime numbers are odd. 1 is neither a prime nor composite number.

So, in our problem, we need to find the Largest Factor of a given number which is also a prime.

Given 13195, the prime factors are 5, 7, 13 and 29. Here 29 is our largest prime factor.

We need to find the Largest prime factor for 600851475143.

---

Approach

The approach here is to factorize the given number with a divisor starting from 2 and update the max with the divisor.

Here is how it is approached,

• Step: 1 - Initialise max to the lowest number possible. max = 0

• Step-2 - While the number n is divisible by 2, then assign max = 2 and divide n by 2. Continue this while loop till the number n is divisible by 2. In this step, we remove all possible even factors.

• Step-3 - Once the while loop(in step-2) finishes, n will be odd. Now while n is divisible by 3, then assign max = 3 and divide n by 3. Continue this while loop till the number n is divisible by 3. In this step, we remove all possible 3 factors

• Step-4 - We loop over all the possible odd factors and update the max to the largest prime factor. Now start a loop from i = 5 to the square root of n.

  • Step-4a - While i divides n, assign max = i, and divide n by i. After i fails to divide n, end this while

  • Step-4b: While i + 2 divides n, assign max = i + 2, and divide n by i + 2. After i + 2 fails to divide n, end this while

  • After both while, increment i by 6 and continue. In this way, we will iterate only for integers that do not have prime factors 2 and 3

• Check if n greater than 4. If so, then that would be the largest prime number factor or else max will be the largest prime factor.

---

Solution

function largestPrimeFact(n) {
    let max = 0;

   while(n % 2 == 0) {
        n /= 2; // Equivalent to n = n/2 OR n >>= 1(Right shift assignment)
        max = 2;
    }

    while(n % 3 == 0) {
        n /= 3; // Equivalent to n = n/3
        max = 3;
    }

    for (let i = 5; i <= Math.sqrt(n); i += 6) {
        while (n % i == 0) {
            max = i;
            n /= i; // Equivalent to n = n/i
        }

        while (n % (i + 2) == 0) {
            maxPrime = i + 2;
            n = n / (i + 2);
        }
    }

    return n > 4 ? n : max;
}
console.time("L2");
console.log(largestPrimeFact(600851475143)); // 6857
console.timeEnd("L2"); // L2: 0.155029296875 ms

I have another approach here on GitHub, using a straightforward while loop solution and it throws a timeout error for a very big number on HackerRank. You can find the code here 03.

If you have another or a better solution, please leave it in the comments below.

For the other Project Euler Solutions, please follow the series Project Euler Solutions in JS.

Thank you!

Note:

1. Right Shift Assignment (>>=).

2. I have created a sheet with the iterations for both approaches here.