C Program to find LCM and HCF of two numbers

What is LCM and HCF?

LCM or Least common multiple of two numbers is the smallest number that can be evenly divisible by both of those numbers: For example: LCM of 4, 10 is 20, LCM of 4, 3 is 12.

HCF or Highest common factor, also known as GCD (Greatest common divisor) of two numbers is the highest number which is evenly divisible by both of those numbers. For example: HCF of 210, 45 is 20, HCF of 6, 18 is 6.

Euclid’s Algorithm to find the HCF

Here are the steps to calculate HCF using Euclid’s Algorithm:

1. Enter two positive integer a and b.
2. If a < b, then swap the values of a and b.
3. Divide a by b and get the remainder. If remainder is 0, then b is the HCF, otherwise go to step 4.
4. Assign the value of b to a and remainder to b, then go to step 3 again.

Once we have calculated the HCF, LCM can be easily computed using the following relation:

$LCM(A, B) = \frac{A*B}{HCF(A,B)}$

The following is a C program to calculate LCM and HCF of two numbers:

Expected Output:

1st run:

2nd run:

How it works

The following table demonstrates what happens at each iteration of the while loop in the calculate_hcf() function, assuming larger = 210 and smaller = 45:

Iteration remainder sum  n
After 1st iteration rem = larger % smaller = 210%45 = 30    larger = 45 smaller = 30
After 2nd iteration rem = 45%30 = 15    larger = 30 smaller = 15
After 3rd iteration rem = 30%15 = 0    larger = 15 smaller = 0

Related Programs: