Project Euler #03 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:

Right Shift Assignment (>>=).
I have created a sheet with the iterations for both approaches here.

Project Euler: #3 - Largest prime factor

Comments

Project Euler: JS Solution Explained!

Project Euler: #4 - Largest palindrome product

More from this blog

What is JavaScript and How It Powers Modern Websites

Project Euler: #17 - Number letter counts

Project Euler: #16 - Power digit sum

Project Euler: #15 - Lattice paths

Project Euler: #14 - Longest Collatz sequence

Problem

Problem Description

Approach

Solution

Command Palette

Comments

Project Euler: JS Solution Explained!

Project Euler: #4 - Largest palindrome product

More from this blog

Problem

Problem Description

Approach

Solution