Find the largest prime factor

An algorithm to find the largest prime factor of a given number.

We will implement a simple algorithm to find the largest prime factor in javascript.

Example

Input:
600851475143
151
256987513645261
231412151232312

Output:
6857
151
36712501949323
9642172968013

Implementation

• We will use a variable having value 2 and loop till the this variable is less than square root of the given number.
• In each iteration will reduce the given number if the number is divisble by the variable.
• In the end we will have the largest prime factor and we will return it.
• Everything is written in ES6.

  let largetPrimeFactor = (num) => {
     //start from 2
     let i = 2;
    
     //loop till the given number is less than the square root of the num
     while(i * i < num) {

      //reduce the number till it is divisible by i
       while(num % i === 0) {
          num /= i;
       }

     //increment i
     i++;
   }
   
   //return the reduced num
   return num;
}

Input:
console.log(largetPrimeFactor(600851475143));    
console.log(largetPrimeFactor(151));
console.log(largetPrimeFactor(256987513645261));
console.log(largetPrimeFactor(231412151232312));

Output:
6857
151
36712501949323
9642172968013

Time complexity: O(sqrt(n)).
Space complexity: O(1).

Time and Space complexity

• We are looping until the square root of the given number which will take O(sqrt(n)), The inner loop in which reduction will occur is not so frequent so it can be neglected, so Time complexity is O(sqrt(n)).
• We are using constant space, so Space complexity is O(1).