### 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 --------------------------------