One of the oldest and finest method to calculate GCD and LCM using Euclids algorithm.

Euclid’s algorithm gives us a process for finding the GCD of 2 numbers. From the larger number, subtract the smaller number as many times as you can until you have a number that is smaller than the small number. (or without getting a negative answer) Now, using the original small number and the result, a smaller number, repeat the process. Repeat this until the last result is zero, and the GCD is the next-to-last small number result.

Example: Find the GCD (18, 27)

27 - 18 = 9

18 - 9 - 9 = 0

So, the GCD of 18 and 27 is 9, the smallest result we had before we reached 0.

PROGRAM:

#include <stdio.h>
int main()
{
    int num1, num2, gcd, lcm, remainder, numerator, denominator;
    printf("Enter two numbersn");
    scanf("%d %d", &num1, &num2);
    if (num1 > num2)
    {
        numerator = num1;
        denominator = num2;
    }
    else
    {
        numerator = num2;
        denominator = num1;
    }
   remainder   = numerator % denominator;
    while (remainder != 0)
    {
        remainder   = numerator % denominator;
        numerator   = denominator;
        denominator = remainder;
    }
    gcd = numerator;
    lcm = num1 * num2 / gcd;
    printf("GCD of %d and %d = %dn", num1, num2, gcd);
    printf("LCM of %d and %d = %dn", num1, num2, lcm);
}

 

OUTPUT:

Enter two numbers
15
25
GCD of 15 and 25 = 5
LCM of 15 and 25 = 75
--------------------------------