Program to find GCD and LCM using Euclids Algorithm in C++

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

--------------------------------