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

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 |
#include <stdio.h> // Iterative function to calculate gcd of two numbers // using Euclid’s Algorithm (basic version) int euclid(int a, int b) { // do until the two numbers become equal while (a != b) { // replace larger number by its difference with the smaller number if (a > b) a = a - b; else b = b - a; } return a; // or b (since both are equal) } // main function int main() { int a = 30; int b = 50; printf("euclid(%d, %d) = %d", a, b, euclid(a, b)); return 0; } |

`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

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 |
#include <stdio.h> // Iterative function to calculate gcd of two numbers // using Euclid’s Algorithm int euclid(int a, int b) { int q, r; // loop till remainder is 0 while (b > 0) { q = a / b; // quotient r = a - q * b; // remainder // or we can simply use (a % b) to calculate r // a becomes b and b becomes r (a % b) a = b; b = r; } return a; } // main function int main() { int a = 2740; int b = 1760; printf("euclid(%d, %d) = %d", a, b, euclid(a, b)); return 0; } |

`Output:`

euclid(2740, 1760) = 20

## Recursive

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 |
#include <stdio.h> // Recursive function to calculate gcd of two numbers // using Euclid’s Algorithm int euclid(int a, int b) { // if the remainder is 0, return second number if (b == 0) return a; int q = a / b; // quotient int r = a - q * b; // remainder // or we can simply use a % b to calculate r // a becomes b and b becomes r (a % b) return euclid(b, r); } // main function int main() { int a = 2740; int b = 1760; printf("euclid(%d, %d) = %d", a, b, euclid(a, b)); return 0; } |

`Output:`

euclid(2740, 1760) = 20

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

## C

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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <stdio.h> #include <stdlib.h> // Iterative function to calculate gcd of two numbers // using Euclid’s Algorithm int euclid(int a, int b) { int r; // loop till remainder is 0 while (b > 0) { // calculate remainder r = a % b; // a becomes b and b becomes r a = b; b = r; } return a; } // main function int main() { FILE *in, *out; in = fopen("input.txt", "r"); if (in == NULL) { printf("Cannot open source file.\n"); exit(1); } out = fopen("output.txt", "w"); if (out == NULL) { printf("Cannot open destination file.\n"); exit(1); } int a, b; char ch; // do till end-of-file is reached while (!feof(in)) { // read next pair of input from the file fscanf(in, "%d %d", &a, &b); // calculate gcd and print to the output file fprintf(out, "euclid(%d, %d) = %d\n", a, b, euclid(a, b)); // go to next line ch = getc(in); } // close input and output file stream fclose(out); fclose(in); return 0; } |

`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 🙂

## Leave a Reply