# 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**

```javascript
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](https://github.com/sansk/project-euler-solutions-javascript/tree/main/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.**](https://theintrovertcoder.hashnode.dev/series/project-euler)

Thank you!

**Note:**

1. [Right Shift Assignment (&gt;&gt;=).](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Right_shift_assignment)
    
2. I have created a sheet with the iterations for both approaches [here.](https://docs.google.com/spreadsheets/d/1whvhQA6PqxPjWK0OgVYgsW1i2J3sXcB_xZ61MuopfPM/edit?usp=sharing)