使用Euclidean算法计算最大公约数

本文的copyleft归[e-mail]所有，使用GPL发布，可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接，严禁用于任何商业用途。
作者：[e-mail]
博客：linuxfocus.blog.chinaunix.net  

今天开始重新学习算法，以一个简单的算法题目开始吧。

使用Euclidean算法计算最大公约数。先介绍一下Euclidean算法。下面是来自wiki的介绍

The GCD of two numbers is the largest number that divides both of them without leaving a remainder. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the smaller number is subtracted from the larger number. For example, 21 is the GCD of 252 and 105 (252 = 21 × 12; 105 = 21 × 5); since 252 − 105 = 147, the GCD of 147 and 105 is also 21. Since the larger of the two numbers is reduced, repeating this process gives successively smaller numbers until one of them is zero. When that occurs, the GCD is the remaining nonzero number. 

就是说两个数的最大公约数，等于两数之差与较小数的最大公约数。

下面是C代码的实现

unsigned int get_greatest_common_divisor(unsigned int u, unsigned int v)
{
    unsigned int t;
    while (u > 0) {
        if (u < v) {
            t = u;
            u = v;
            v = t;
        }
        u = u-v;
    }

    return v;
}

在《Algorithms in C》的课后题中，要求计算3个数的最大公约数。这个解答仍然可以通过上面计算两个数的最大公约数的函数来实现。如有abc三个数，分别求出ab的最大公约数d，然后再计算d与c的最大公约数。

unsigned int get_greatest_common_divisor_of_two_num(unsigned int u, unsigned int v)
{
    unsigned int t;
    while (u > 0) {
        if (u < v) {
            t = u;
            u = v;
            v = t;
        }
        u = u-v;
    }

    return v;
}

unsigned int get_greatest_common_divisor_of_three_num(unsigned int x, unsigned int y, unsigned z)
{
    unsigned int a = get_greatest_common_divisor_of_two_num(x, y);

    return get_greatest_common_divisor_of_two_num(a, z);
}

在网上还可以搜到一种通过取模来求取GCD的算法，而且也说是Euclid算法。这让我很困惑啊。。。怎么会有两种说法呢？不过还是以英文为主吧。所以还是认为Euclid算法是通过这个减法来求取GCD吧，这个要比取模运算高效。

参考：《Algorithms in C》