JavaScript Program to Find LCM of Two Numbers

You can find the LCM of two numbers in JavaScript by first finding their GCD using a function with while loop, then calculating LCM as (a * b) / gcd.

Examples

Input6, 8

Output24

Input12, 15

Output60

Input7, 5

Output35

How to Think About It

To find the LCM of two numbers, first find their greatest common divisor (GCD) by repeatedly using the remainder until one number becomes zero. Then, use the formula LCM = (first number * second number) / GCD to get the least common multiple.

Algorithm

1

Get two numbers as input.

2

Find the GCD of the two numbers using the Euclidean algorithm.

3

Calculate the LCM by dividing the product of the two numbers by the GCD.

4

Return or print the LCM.

Code

javascript

function gcd(a, b) {
  while (b !== 0) {
    const temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

console.log(lcm(6, 8));

Output

24

Dry Run

Let's trace lcm(6, 8) through the code

1

Start gcd with a=6, b=8

a=6, b=8

2

Calculate remainder and swap

temp=8, b=6 % 8 = 6, a=8

3

Next iteration gcd with a=8, b=6

a=8, b=6

4

Calculate remainder and swap

temp=6, b=8 % 6 = 2, a=6

5

Next iteration gcd with a=6, b=2

a=6, b=2

6

Calculate remainder and swap

temp=2, b=6 % 2 = 0, a=2

7

b is zero, gcd is a=2

gcd=2

8

Calculate lcm = (6 * 8) / 2

lcm = 48 / 2 = 24

a	b	temp	b after %	a after swap
6	8	8	6	8
8	6	6	2	6
6	2	2	0	2

Why This Works

Step 1: Find GCD using Euclidean algorithm

The code uses a while loop to repeatedly replace a and b with b and a % b until b becomes zero, which gives the greatest common divisor.

Step 2: Calculate LCM using GCD

Once GCD is found, the LCM is calculated by dividing the product of the two numbers by the GCD using the formula LCM = (a * b) / GCD.

Step 3: Return the LCM

The function returns the LCM value, which is the smallest number divisible by both input numbers.

Alternative Approaches

Using a loop to find LCM directly

javascript

function lcmLoop(a, b) {
  let max = a > b ? a : b;
  while (true) {
    if (max % a === 0 && max % b === 0) {
      return max;
    }
    max++;
  }
}
console.log(lcmLoop(6, 8));

This method checks multiples starting from the larger number until it finds a common multiple. It is simpler but slower for large numbers.

Recursive GCD function

javascript

function gcdRecursive(a, b) {
  if (b === 0) return a;
  return gcdRecursive(b, a % b);
}
function lcm(a, b) {
  return (a * b) / gcdRecursive(a, b);
}
console.log(lcm(6, 8));

This uses recursion for GCD calculation, which is elegant and concise but may cause stack overflow for very large inputs.

Complexity: O(log(min(a, b))) time, O(1) space

Time Complexity

Finding GCD using the Euclidean algorithm takes O(log(min(a, b))) time because each step reduces the problem size significantly.

Space Complexity

The algorithm uses constant extra space O(1) as it only stores a few variables for calculations.

Which Approach is Fastest?

Using the Euclidean algorithm for GCD and then calculating LCM is much faster than looping through multiples, especially for large numbers.

Approach	Time	Space	Best For
GCD with Euclidean Algorithm	O(log(min(a,b)))	O(1)	Large numbers, efficient
Loop to find LCM	O(a*b) in worst case	O(1)	Small numbers, simple logic
Recursive GCD	O(log(min(a,b)))	O(log(min(a,b))) due to call stack	Elegant code, moderate input sizes