The greatest common denominator, or GCD, between two numbers is the greatest integer that divides both given numbers. Writing a C# program that can calculate the greatest common denominator (GCD) of large numbers quickily would be very useful. The first idea that comes to mind is perhaps to write a for loop to check all numbers that are less than the pair of numbers to find the GCD. However there is a more efficient way using the Euclidean Algorithm.

``````/// <summary>
/// Returns the Greatest Common Denominator of two integers using
/// the Euclidean Algorithm recursively.
/// </summary>
public int GCDRecursive(int a, int b)
{
//Base cases
if (a == 0)
{
return b;
}

if (b == 0)
{
return a;
}

if (a > b)
{
return GCDRecursive(a % b, b);
}
else
{
return GCDRecursive(a, b % a);
}
}

/// <summary>
/// Returns the Greatest Common Denominator of two integers using
/// the Euclidean Algorithm non-recursively.
/// </summary>
public int GCD(int a, int b)
{
while (a != 0 && b != 0)
{
if (a > b)
{
a %= b;
}
else
{
b %= a;
}
}

if (a == 0)
{
return b;
}
else
{
return a;
}
}``````