GCD of 2 numbers

18 Sep 2017

Greatest Common Divisor (GCD) of 2 or more numbers is a number that can divide all integers. For example, when a = 2 and b =4 then GCD(2,4) = 2;

i.e., 2 is the largest number that divides both a and b.

The typical GCD implementation is done using recursion function (the depth of recursion is limited by the underlying system) as follows

int gcd(int a, int b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 

There is an alternative method using Euclidean algorithm, that calculates GCD of two integer numbers using simple loop.

static int GCD(int n, int m)
{
  a = Math.Max(n, m);
  b = Math.Min(n, m);
  int r;
  while (b != 0)
  {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

GCD can be further used to find Least Common Multiplier(LCM) between numbers.
The algorithm is as follows

static int LCM(int a, int b)
{
   return (a * b) / GCD(a, b);
}