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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#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:

1 2 3 4 5 6 7 8 9 10 11 |
Enter two numbers 15 25 GCD of 15 and 25 = 5 LCM of 15 and 25 = 75 -------------------------------- |

## Leave a Reply