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

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 53 54 |
/*********************************************** * 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 | 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:**