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:

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:

\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 // 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: