Bash Script to Find LCM of Two Numbers

Use a Bash script that calculates the greatest common divisor (GCD) first, then finds the LCM using lcm = (a * b) / gcd. For example: gcd() { while [ $b -ne 0 ]; do t=$b; b=$((a % b)); a=$t; done; echo $a; }; lcm=$(( (num1 * num2) / $(gcd) )).

Examples

Input6 8

Output24

Input15 20

Output60

Input7 7

Output7

How to Think About It

To find the LCM of two numbers, first find their greatest common divisor (GCD) using the Euclidean algorithm. Then, use the formula LCM = (number1 * number2) / GCD. This works because the product of two numbers equals the product of their GCD and LCM.

Algorithm

1

Get two input numbers from the user.

2

Calculate 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

Print the LCM.

Code

bash

#!/bin/bash
read -p "Enter two numbers: " a b
function gcd() {
  local x=$1
  local y=$2
  while [ $y -ne 0 ]; do
    local temp=$y
    y=$(( x % y ))
    x=$temp
  done
  echo $x
}
g=$(gcd $a $b)
lcm=$(( (a * b) / g ))
echo "LCM of $a and $b is $lcm"

Output

Enter two numbers: 6 8
LCM of 6 and 8 is 24

Dry Run

Let's trace the input 6 and 8 through the code

1

Input numbers

a=6, b=8

2

Calculate GCD

x=6, y=8; y != 0, temp=8; y=6%8=6; x=8 x=8, y=6; y != 0, temp=6; y=8%6=2; x=6 x=6, y=2; y != 0, temp=2; y=6%2=0; x=2 GCD=2

3

Calculate LCM

LCM = (6 * 8) / 2 = 48 / 2 = 24

Iteration	x	y	temp	y after modulo
1	6	8	8	6
2	8	6	6	2
3	6	2	2	0

Why This Works

Step 1: Why find GCD first?

The GCD helps us find the LCM because the product of two numbers equals the product of their GCD and LCM.

Step 2: How Euclidean algorithm works

It repeatedly replaces the larger number by the remainder of dividing the larger by the smaller until the remainder is zero, leaving the GCD.

Step 3: Calculating LCM

Divide the product of the two numbers by their GCD to get the LCM.

Alternative Approaches

Using a loop to find LCM

bash

#!/bin/bash
read -p "Enter two numbers: " a b
max=$(( a > b ? a : b ))
while true; do
  if (( max % a == 0 && max % b == 0 )); then
    echo "LCM of $a and $b is $max"
    break
  fi
  ((max++))
done

This method is simpler but slower for large numbers because it checks multiples one by one.

Using bc for arithmetic

bash

#!/bin/bash
read -p "Enter two numbers: " a b
gcd=$(echo "define gcd(a,b){if(b==0)return a; return gcd(b,a%b);} gcd($a,$b)" | bc)
lcm=$(( (a * b) / gcd ))
echo "LCM of $a and $b is $lcm"

Uses bc calculator for GCD, good for more complex math but requires bc installed.

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

Time Complexity

The Euclidean algorithm for GCD runs in O(log(min(a,b))) time, which dominates the calculation. The LCM calculation is a simple arithmetic operation.

Space Complexity

The script uses a fixed number of variables and no extra data structures, so space complexity is O(1).

Which Approach is Fastest?

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

Approach	Time	Space	Best For
Euclidean GCD + formula	O(log(min(a,b)))	O(1)	Efficient for all input sizes
Loop checking multiples	O(n) worst case	O(1)	Simple but slow for large numbers
Using bc calculator	Depends on bc implementation	O(1)	When bc is available and for complex math