Find the Greatest Common Divisor (GCD)

Problem: Given two non-negative integer a and b, find the greatest common divisor.

Solution: A very efficient algorithm is Euclid’s algorithm.  The main idea here is GCD(a, b) =  GCD(b, a mod b). Therefore, the code is straightforward:

int GCD(int a, int b)
{
   if(b==0) return a;
  
   return GCD(b, a mod b);
}