两个整数的最大公约数(greatest common divisor,GCD)是能被这两个整数整除的最大数。下面的程序给出了一个求两个整数m和n的最大公约数的穷举算法。穷举(brute force)法指使用最简单和直接，或者非常明显的方式解决问题的一种算法。结果是，为了解决一个给定问题，这样的算法相比更聪明或者更复杂的算法而言，可能导致做更多的工作。另外一方面，穷举算法相对于复杂的算法而言，通常更加易于实现，并且因为其简单性，有时候可以更加高效。
穷举算法检测k(k=2,3,4,…)是否是n1和n2的公约数，直到k大于n1或n2。该算法可以如下描述：
public static int gcd(int m, int n) {
int gcd = 1;
for (int k = 2; k <= m && k <= n; k++) {
if (m % k == 0 && n % k == 0)
gcd = k;
}
return gcd;
}
假设m>=n，那么，显然该算法的复杂度是O(n)
是否还有求最大公约数的更好的算法？不从1向上开始查找可能的除数，而是从n开始向下查找，这样会更高效。一旦找到一个除数，该除数就是最大公约数。因此，可以使用下面的循环来改进算法：
for(int k=n;k>=1;k–){
if(m%k==0 && n%k==0){
gcd=k;
break;
}
}
这个算法比前一个效率更高，但是它的最坏情况的时间复杂度依旧是O(n)，数字n的除数不可能比n/2大。因此，可以使用下面的循环进一步改进算法:
for(int k=m/2;k>=1;k–)(
if(m%k==0 && n%k==0){
gcd=k;
break;
}
}
但是，该算法是不正确的，因为n可能会是m的除数。这种情况必须考虑到。
假设m>=n，那么这个for循环最多执行n/2次，比前一个算法节省了一半的运行时间，该算法的时间复杂度仍然是O(n)，但实际上，它比上面的算法快得多。
注意：大O标记提供了对算法效率的一个很好的理论上的估算。但是，两个算法即使有相同的时间复杂度，它们的效率也不一定相同。如前面的例子所示，两个算法具有相同的复杂度，但实际上，后面的算法显然更好些。
求最大公约数的一个更有效的算法是在公元前300年左右由欧几里得发现的，这是最古老的著名算法之一。它可以递归地定义如下：
用gcd(m,n)表示整数m和n的最大公约数：
如果m%n为0，那么gcd(m,n)为n。
否则，gcd(m,n)就是gcd(n,m%n)o
不难证明这个算法的正确性。假设m%n=r，那么，m=qn+r，这里的q是m/n的商。能整除m和n的任意数字都必须也能整除r。因此，gcd(m,n)和gcd(n,r)是一样的，其中r=m%n。
最好的情况是当m%n为0的时候，算法只用一步就能找出最大公约数。分析平均情况是很困难的。然而，我们可以证明最坏情况的时间复杂度是O(logn)。
假设m>=n，我们可以证明m%n<m/2，如下所示：
如果n<=m/2，那么m%n<m/2，因为根除以n的余数总是小于n。
如果n>m/2，那么m%n=m-n<m/2o因此，m%n<m/2。
欧几里得的算法递归地调用gcd方法。它首先调用gcd(m,n)，接着调用gcd(n,m%n),然后是gcd(m%n,n%(m%n)),以此类推，如下所示：
gcd(m,n)
= gcd(n,m%n)
= gcd(m%n,n%(m%n))
=…
因为m%n<m/2且n%(m%n)<n/2，所以传递给gcd方法的参数在每两次迭代之后减少一半。在调用gcd两次之后，第二个参数小于n/2。在调用gcd四次之后，第二个参数小于n/4。在调用gcd六次之后，第二个参数小于n/23o假设k是调用gcd方法的次数。在调用gcd方法k次之后，第二个参数小于n/2(k/2)，它是大于或等于1的。也就是
因此，k<=2logn。所以该gcd方法的时间复杂度是O(logn)。
最坏情况发生在两个数导致了最大分离的时候。事实证明，两个连续的斐波那契数会造成最大分离的情况。回顾斐波那契数列是从0和1开始，然后后一个数都是前两个数的和，例如：
0 1 1 2 3 5 8 13 21 34 55 89…
这个数列可以递归地定义为
fib(0)=0;
fib(1)=1;
fib(index)=fib(index-2)+fib(index-1);index>=2
对于两个连续的斐波那契数fib(index)和fib(index-1),
gcd(fib(index), fib(index − 1))
= gcd(fib(index − 1), fib(index − 2))
= gcd(fib(index − 2), fib(index − 3))
= gcd(fib(index − 3), fib(index − 4))
= . . .
= gcd(fib(2), fib(1))
= 1
因此，gcd方法被调用的次数和下标相等。我们可以证明index<=1.441ogn，其中n=fib(index-1)。这是一个比index<=2logn更严格的限定。
转载请注明：陈童的博客 » 使用欧几里得算法求最大公约数