欧几里德算法求最大公约数

技术算法
最大公约数, 欧几里德算法

前言

最近看算法书籍时，发现欧几里德算法，再次对欧几里德等古代的学者深感佩服。算法简单巧妙，更重要的是，它背后所隐藏的对问题通用的解决方法——对于那些无法直接求解的问题，通过发现其潜在的规律，使用循环迭代逐步减小问题的难度，最终得到问题的结果。如今在计算机科学里无处不充斥着这样的方法，但是我们古人早在几千年前就已经使用得炉火青纯了。

欧几里德算法思路

欧几里德算法是求解两个数的最大公约数问题的方法。对于我们来说两个较小的数字，可以比较容易的推算出来他们的最大公约数，但是稍微大一点的数字，就无法直接心算求得了。

我们使用程序来解决这问题，普通解决思路的求法就是从小大一个个尝试，直到扫描完从0到两个数中的小者这个区间内的所有数字，输出一个能够同时被两个数整除的最大数字。这个方法的算法的时间复杂度是线性的。

而欧几里德算法，巧妙的利用了：两个数的公约数也是，其中任意一个数与两者模的最大公约数。

例如：求A,B的最大公约数是C，假定A>B，那么A和A%B的最大公约数也是C，B和A%B的最大公约数也是C。这样我们就将两个求两个大数A，B的最大公约数问题，转化为求B于A%B这样两个更小的数的最大公约数。经过逐层迭代，问题最终能够转化为我们可以直接求得的两个很小的数字的最大公约数问题。

当然对于计算机而言，它不能判断数字减小到什么时候可以直接看出来最大公约数，需要有一个明确的条件告诉它循环结束。这个调节就是当两个数的模等于0时，循环结束，最大公约数就是当前小的哪个数字。

证明

继承上述的例子：A = K1 x C，B = K2 x C，且K1和K2互质，A和B的模D = A % B = (K1 - K2 x n) x C，所以A、B、D有共约数C，有因为K1和K2互质，所以K2与K1-K2 x n是互质的，所以C是B、D最大公约数，所以A和B的最大共约数与B和D的最大共约数一样。

在逐步迭代过程中，D的系数K1-K2 x n会不断减小，最终等于1，这个时候D = C，整个过程结束。

使用欧几里德算法，可以让求解空间域快速收敛，算法效率大大提高。

代码

虽然使用循环会更高效，但是写为递归的形式会更容易理解，所以以下为递归实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int do_gcd(int max, int min)
{
    return min?do_gcd(min, max%min):max;
}

int gcd(int a, int b)
{
    if(a == 0 || b == 0)
        return 0;
    
    if(a > b)
        return do_gcd(a, b);
    else
        return do_gcd(b, a);
}
Compartir