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);
}