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.





Be the first to comment

Leave a Reply