# C Program to find LCM and HCF of two numbers

Last updated on September 23, 2020

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

- Enter two positive integer
`a`

and`b`

. - If
`a < b`

, then swap the values of`a`

and`b`

. - Divide
`a`

by`b`

and get the remainder. If remainder is`0`

, then`b`

is the HCF, otherwise go to step 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:

\begin{gather*}

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

\end{gather*}

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | ```
/***********************************************
* C Program to find LCM and HCF of two numbers
************************************************/
#include<stdio.h> // include stdio.h
int main()
{
int a, b;
printf("Enter two numbers: ");
scanf("%d %d", &a, &b);
printf("HCF = %d\n", calculate_hcf(a, b));
printf("LCM = %d\n", calculate_lcm(a, b));
return 0;
}
int calculate_hcf(int smaller, int larger)
{
// Finding HCF using Euclid's Algorithm
// https://en.wikipedia.org/wiki/Euclidean_algorithm
int rem, tmp;
if(larger < smaller)
{
tmp = larger;
larger = smaller;
smaller = tmp;
}
while(1)
{
rem = larger % smaller;
if(rem == 0)
{
return smaller;
}
larger = smaller;
smaller = rem;
}
}
int calculate_lcm(int a, int b)
{
// lcm = product of two numbers / hcf
return (a * b) / calculate_hcf(a, b);
}
``` |

**Expected Output:** 1st run:

1 2 3 | ```
Enter two numbers: 3 4
HCF = 1
LCM = 12
``` |

2nd run:

1 2 3 | ```
Enter two numbers: 210 45
HCF = 15
LCM = 630
``` |

**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 | `rem` |
`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:**

- C Program to check whether a year is a leap year
- C Program to check whether the number is even or odd.
- C Program to find the sum of natural numbers upto N terms
- C Program to find Armstrong numbers
- C Program to find the factorial of a number

Load Comments