1. Home
2. C Programming Examples
3. C Program to find LCM and HCF of two numbers

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<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);
}

Try it now

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:

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