Euclid’s Algorithm to find GCD of two numbers

The Euclid’s algorithm (or Euclidean Algorithm) is a method for efficiently finding the greatest common divisor (GCD) of two numbers. The GCD of two integers X and Y is the largest number that divides both of X and Y (without leaving a remainder).

 


For example,

euclid(30, 50) = 10

euclid(2740, 1760) = 20

 


 

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.

For example, 21 is the GCD of 252 and 105 (252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 147 = 252 – 105.

Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers.

C

Download   Run Code

Output:

euclid(30, 50) = 10

The only problem with the above version is that it can take several subtraction steps to find the GCD if one of the given numbers is much bigger than the other.

A more efficient version of the algorithm replaces the larger of the two numbers by its remainder when divided by the smaller of the two. The algorithm stops when reaching a zero remainder and now the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer.

Iterative

Download   Run Code

Output:

euclid(2740, 1760) = 20

Recursive

Download   Run Code

Output:

euclid(2740, 1760) = 20

We can extend above program to read multiple inputs from file as shown below:

C

Output:

input.txt
2740 1760
6 4

output.txt
euclid(2740, 1760) = 20
euclid(6, 4) = 2

 
 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂