Bash Script to Find HCF of Two Numbers

Use Euclid's algorithm in Bash by repeatedly replacing the larger number with the remainder of the division until the remainder is zero; the last non-zero remainder is the HCF. For example, use while [ $b -ne 0 ]; do temp=$b; b=$((a % b)); a=$temp; done; echo $a.

Examples

Inputa=12, b=15

Output3

Inputa=100, b=25

Output25

Inputa=7, b=13

Output1

How to Think About It

To find the HCF of two numbers, think of repeatedly dividing the larger number by the smaller and replacing the larger with the remainder. When the remainder becomes zero, the smaller number at that point is the HCF. This process is called Euclid's algorithm and works because the HCF does not change when replacing numbers this way.

Algorithm

1

Get two input numbers a and b

2

While b is not zero, do:

3

Calculate remainder of a divided by b

4

Replace a with b and b with the remainder

5

When b becomes zero, a holds the HCF

6

Return a as the HCF

Code

bash

#!/bin/bash
read -p "Enter first number: " a
read -p "Enter second number: " b
while [ $b -ne 0 ]
do
  temp=$b
  b=$((a % b))
  a=$temp
done
echo "HCF is $a"

Output

Enter first number: 12
Enter second number: 15
HCF is 3

Dry Run

Let's trace the input a=12 and b=15 through the code

1

Initial values

a=12, b=15

2

Calculate remainder

temp=15, b=12 % 15 = 12, a=15

3

Next iteration

a=15, b=12

4

Calculate remainder

temp=12, b=15 % 12 = 3, a=12

5

Next iteration

a=12, b=3

6

Calculate remainder

temp=3, b=12 % 3 = 0, a=3

7

Loop ends

b=0, so HCF is a=3

a	b	temp	b after modulo
12	15	15	12
15	12	12	3
12	3	3	0

Why This Works

Step 1: Why use Euclid's algorithm

Euclid's algorithm finds the HCF by using the property that the HCF of two numbers also divides their remainder.

Step 2: How the loop works

The loop keeps replacing the pair (a, b) with (b, a % b) until b becomes zero, shrinking the problem each time.

Step 3: Result when loop ends

When b is zero, a contains the HCF because the remainder is zero and a divides both original numbers.

Alternative Approaches

Using recursive function

bash

#!/bin/bash
hcf() {
  if [ $2 -eq 0 ]; then
    echo $1
  else
    hcf $2 $(( $1 % $2 ))
  fi
}
read -p "Enter first number: " a
read -p "Enter second number: " b
result=$(hcf $a $b)
echo "HCF is $result"

This uses recursion which is elegant but may be less clear for beginners.

Using gcd command (if available)

bash

read -p "Enter first number: " a
read -p "Enter second number: " b
gcd=$(gcd $a $b 2>/dev/null)
if [ $? -eq 0 ]; then
  echo "HCF is $gcd"
else
  echo "gcd command not found"
fi

Some systems have a gcd command, but it's not standard everywhere.

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

Time Complexity

Euclid's algorithm runs in logarithmic time relative to the smaller input because each step reduces the problem size significantly.

Space Complexity

The algorithm uses constant extra space since it only stores a few variables and updates them in place.

Which Approach is Fastest?

The iterative Euclid's algorithm is fastest and simplest; recursion adds overhead, and external commands may not be available.

Approach	Time	Space	Best For
Iterative Euclid's Algorithm	O(log(min(a,b)))	O(1)	General use, efficient
Recursive Euclid's Algorithm	O(log(min(a,b)))	O(log(min(a,b)))	Readable code, small inputs
gcd command	Depends on implementation	Depends on implementation	Quick if available, not portable