Find the LCM of two numbers in javascript

An algorithm to find the lcm of two numbers.

We will implement two different algorithms to find the lcm of two numbers in javascript. Everything will be written in ES6.

Example

Input:
15 20
5 7

Output:
60
35

With using GCD.

Implementation

• There is a mathematical formula to find the LCM of two number using GCD (n1 x n2) / GCD(n1, n2).
• We will be using this to find the result.

let lcm = (n1, n2) => {
  //Find the gcd first 
  let gcd = gcd(n1, n2);

  //then calculate the lcm
  return (n1 * n2) / gcd;
}

Input:
console.log(lcm(15, 20));
console.log(lcm(5, 7));

Output:
60
35

Time complexity: O(log(a) + log(b)).
Space complexity: O(1).

Time and Space complexity

• We are first finding the GCD of the given number which will take O(log(a) + log(b)) and then returning the LCM which will take O(1), so Time complexity is O(log(a) + log(b)).
• We are using constant space, so Space complexity is O(1).

Without using GCD.

Implementation

• We separate the smallest and the biggest number from both the input numbers.
• Then we will find the lcm by repeatedly adding the largest till it is divisible by the smallest number.

let lcm = (n1, n2) => {
  //Find the smallest and biggest number from both the numbers
  let lar = Math.max(n1, n2);
  let small = Math.min(n1, n2);
  
  //Loop till you find a number by adding the largest number which is divisble by the smallest number
  let i = lar;
  while(i % small !== 0){
    i += lar;
  }
  
  //return the number
  return i;
}

Input:
console.log(lcm(20, 15));
console.log(lcm(5, 7));

Output:
60
35

Time complexity: NA.
Space complexity: O(1).

Time and Space complexity

• This is NP complete problem as there is nothing specific about how much time it will take, so Time complexity is NA.
• We are using constant space, so Space complexity is O(1).