Euclid’s Algorithm to find GCD of two numbers
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 X and Y without leaving a remainder.
For example,
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 (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.
The following C program demonstrates it:
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 |
#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 the 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) } 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 one. 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.
The iterative and recursive implementation can be seen below in C:
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 |
#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; } 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 the 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); } 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 the above program to read multiple inputs from a file, as shown below in C:
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 |
#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; } int main() { FILE *in, *out; in = fopen("input.txt", "r"); if (in == NULL) { printf("Cannot open the source file.\n"); exit(1); } out = fopen("output.txt", "w"); if (out == NULL) { printf("Cannot open the destination file.\n"); exit(1); } int a, b; char ch; // do till the end-of-file is reached while (!feof(in)) { // read the 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 the 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
Also See:
Extended Euclidean Algorithm – C, C++, Java, and Python Implementation
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)