C program to find LCM and HCF of two numbers

In this example, you will learn to calculate the LCM (Lowest common multiple) and HCF (Highest common factor) of two numbers entered by the user.

Prerequisite to understand the below example code:

Before understanding the code let’s understand what is LCM and HCF. It will help to understand the C code.

LCM: In arithmetic and number theory, the least common multiple of two integers ‘a’ and ‘b’ is the smallest number that is a multiple of both ‘a’ and ‘b’.

Example: LCM of 4 and 6:

Multiples of 4 are: 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48,...

Multiples of 6 are: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, ...

Common multiples of 4 and 6 are the numbers that are in both lists: 12, 24, 36, 48, ...

In this list, the smallest number is 12. Hence, the least common multiple is 12.

 

HCF: The Highest Common Factor (HCF) of two numbers ‘a’ and ‘b’ is the highest possible number that divides both ‘a’ and ‘b’ completely.

Example: HCF of 30 and 42

Factors of 30 are: 1, 2, 3, 5, 6, 10, 15, 30

Factors of 42 are: 1, 2, 3, 6, 7, 14, 21, 42

Common Factors of 30 and 42 are the numbers that are in both lists: 1, 2, 3, 6

In this list, the greatest factor is 6. Hence, the highest common factor is 6.

 

#include<stdio.h>

//  Finding HCF using Euclid's Algorithm
//  https://en.wikipedia.org/wiki/Euclidean_algorithm
int calculateHcf(int smaller, int larger)
{
    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 calculateLcm(int a, int b)
{
    // lcm = product of two numbers / hcf
    return (a * b) / calculateHcf(a, b);
}

int main()
{
    int a, b,ret;

    printf("Enter two numbers: ");
    scanf("%d%d",&a,&b);

    ret	= calculateHcf(a, b);
    printf("HCF = %d\n", ret);

    ret	= calculateLcm(a, b);

    printf("LCM = %d\n", ret);

    return 0;
}

Output:

Enter two numbers: 6 8
HCF = 2
LCM = 24

Recommended Post: