.NET 1.1+

Euclid's Algorithm

Euclid's algorithm, also known as the Euclidean algorithm, can be used to efficiently calculate the greatest common divisor (GCD) for two integer values. This article describes the algorithm and provides several C# methods that calculate the GCD.

Greatest Common Divisor

Euclid's algorithm, which is often called the Euclidean algorithm, is an algorithm described by the Greek mathematician, Euclid of Alexandria. The algorithm seeks to calculate the greatest common divisor (GCD) of two arbitrarily large integers; the GCD being the largest whole number that can the two values can be divided by without remainder. The algorithm uses the fact that when two numbers share a common divisor, subtracting the smaller number from the larger yields a result that also shares the common divisor.

As an example, let's consider the values 210 and 126. The GCD of these two numbers is 42. Note that 210 / 42 = 5 and 126 / 4 = 3. If we were to subtract the smaller value from the larger we get 210 - 126 = 84. This too divides equally by 42, giving the result, 2.

If the process of subtracting the smaller number from the larger is repeated, eventually one of the values will become zero. At this point, the other value will contain the GCD for the original pair. This iterative process for our example values yields the following results:

210 - 126 = 84
126 - 84 = 42
84 - 42 = 42
42 - 42 = 0

The final calculation gives a zero result, which would leave the two values 42 and zero. Therefore, the GCD is the value 42.

Implementing Euclid's Algorithm

For the first implementation of the algorithm we will follow the steps described above directly. We will create a static method that has two integer parameters and returns a third integer containing the GCD. The method is static so that it can be called easily from the Main method of a console application without instantiating objects. You may decide to implement it as an instance method for your own project.

The method has several steps. Initially a while loop is created that will continue processing until one of the values has been reduced to zero. Within the loop the smaller of the two values is subtracted from the larger. Once the loop has exited, one value will be zero and the other will contain the GCD. The GCD is returned by finding the larger of the two values. NB: The code in this article assumes that both integers are positive.

To create the method, add the following code:

public static int GetGCDBySubtraction(int value1, int value2)
{
    while (value1 != 0 && value2 != 0)
    {
        if (value1 > value2)
            value1 -= value2;
        else
            value2 -= value1;
    }
    return Math.Max(value1, value2);
}

To test the method, try executing the following command. This finds the GCD of 116,150 and 232,704. The result should be 202.

int gcd = GetGCDBySubtraction(116150, 232704); // 202