# 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: