Skip to main content

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