8. Greatest common divisors

The most obvious way to calculate GCD(A, B) is to simply try all of the values smaller than A and B and see which ones divide both numbers. That method is straightforward and reasonably fast, although it could take a while if A and B are very large. In particular, using this method to find GCD(10370370276, 82962962964) could take a long time.

A faster alternative would be to factor A and B (I'll talk about factoring later in this chapter) and then determine the factors that they have in common.

An even faster alternative was described by Euclid (pronounced yoo-klid) around 300 BC. Because he first described the algorithm, it is called Euclid's algorithm or the Euclidean algorithm.

The idea behind the algorithm is that, if A > B and C evenly divides both A and B, then C must also evenly divide A – B. That leads to the following algorithm:

1. Set remainder = A mod B
2. If remainder is 0, then B is the GCD
3. Otherwise set A = B and B = remainder, and then repeat from step 1

For example, the following steps show the calculation for GCD(180, 48):

1. Remainder = 180 % 48 = 36
2. A = 48, B = 36
3. Remainder = 48 % 36 = 12
4. A = 36, B = 12
5. Remainder = 36 % 12 = 0
6. At this point, the remainder is 0, so the GCD is B, which is 12

This calculation found GCD(180, 48) in only six steps.

The following method uses this algorithm to calculate the GCD:

// Use Euclid's algorithm to find GCD(a, b).
private long GCD(long a, long b)
{
    a = Math.Abs(a);
    b = Math.Abs(b);

    // Pull out remainders.
    for (;;)
    {
        long remainder = a % b;
        if (remainder == 0) return b;
        a = b;
        b = remainder;
    };
}

This code simply takes the absolute values of its inputs a and b, and then follows Euclid's algorithm.

Download the GCD example solution to see additional details.