C Program To Find GCD and LCM of Two Numbers using Euclidean algorithm

Lets write a C program to find GCD / HCF and LCM of Two user entered Numbers using Euclidean algorithm.

Full Forms

GCD: Greatest Common Divisor.
HCF: Highest Common Factor.
LCM: Least common Multiple.

Related Read:
while loop in C programming

Formula To Calculate LCM

Once we get the GCD, we use the below formula to calculate LCM.

LCM = ( num1 * num2 ) / GCD;

Source Code: C Program To Find GCD and LCM of Two Numbers using Euclidean algorithm

 
#include < stdio.h >

int main()
{
    int num1, num2, gcd, lcm, rem, numerator, denominator;

    printf("Enter 2 integer numbers\n");
    scanf("%d%d", &num1, &num2);

    if(num1 > num2)
    {
        numerator   = num1;
        denominator = num2;
    }
    else
    {
        numerator   = num2;
        denominator = num1;
    }

    rem = numerator % denominator;

    while(rem != 0)
    {
        numerator   = denominator;
        denominator = rem;
        rem         = numerator % denominator;
    }

    gcd = denominator;
    lcm = (num1 * num2) / gcd;

    printf("GCD of %d and %d is %d\n", num1, num2, gcd);
    printf("LCM of %d and %d is %d\n", num1, num2, lcm);

    return 0;
}

Output
Enter 2 integer numbers
15
20
GCD of 15 and 20 is 5
LCM of 15 and 20 is 60

C Program To Find GCD and LCM of Two Numbers using Euclidean algorithm

Logic To Find GCD and LCM of Two Numbers using Euclidean algorithm

We find biggest of the 2 numbers entered by the user. Biggest number is assigned to variable numerator and smaller number is assigned to variable denominator. Now reminder is calculated. If the reminder is not equal to zero, then the value of variable denominator is assigned to variable numerator and the value of variable reminder is transferred to variable denominator and once again reminder is calculated – until reminder is zero. Once reminder is zero, gcd will be present in variable denominator.

For list of all c programming interviews / viva question and answers visit: C Programming Interview / Viva Q&A List

For full C programming language free video tutorial list visit:C Programming: Beginner To Advance To Expert