Euclid's Algorithm : GCD of 2 integers

The following example solves a classic elementary problem: “Reduce a given fraction to its lowest terms”, e.g. we want to write 2/3, not 4/6. We solve this problem by finding the greatest common divisor (gcd) of the numerator and the denominator by using the famous approach called Euclid’s algorithm.

C Code
Iterative solution

// Iterative algorithm  
int gcd(int a, int b)  
{  
   int temp;  
  
   while(b)  
   {  
      temp = a % b;  
      a = b;  
      b = temp;  
   }  
  
   return(a);  
}

Recursive solution

// Recursive algorithm  
int gcd\_recurse(int a, int b)  
{  
   int temp;  
   temp = a % b;  
  
   if (temp == 0)  
   {  
      return(b);  
   }  
   else  
   {  
      return(gcd\_recurse(b, temp));  
   }  
}

Driver program

#include <studio.h>  
  
int gcd(int a, int b);  
int gcd\_recurse(int a, int b);  
  
int main()  
{  
  printf("\\nGCD(%2d,%2d) = \[%d\]", 6,4,  gcd(6,4));  
  
 printf("\\nGCD(%2d,%2d) = \[%d\]", 6,4,  gcd\_recurse(6,4));  
  
  return(0);  
}

Thanks.

See also