最大公约数和最小公倍数的求法分析

简介

        求最大公约数和最小公倍数可能是编程中最常见的几个基本问题了。因为他们的基本概念基本上很早的时候就知道了，对他们的求法和他们之间的关系都比较有意思。

基本的数学性质

       先从最大公约数这一部分开始吧。从本身的概念来理解的话，就是说假设D = gcd(A, B)，那么对于A和B这两个数来说，D是他们之间最大的公共因子。假设A > B， 那么既然D是他们的因子，A可以表示成A = SD, B可以表示成B = KD.(S > K)。

 

方法一：

 

        那么，假设给定两个数A,B。我们怎么来求他们的最大公约数呢？一种最直接简单的方法如下：

1.首先对每个数A, B分别求他们的因子，并将这些可以整除的因子保存到一个数组里面。因为之需要计算到最大为该数的求根，所有耗费的计算量分别为根号A和根号B.

 

2. 通过遍历比较两个保存因子的数组，找到相同且最大的一个，那么这个就是所期望的结果。这一步所需要耗费的时间也是根号N级别的。

总的来说，这种方法的时间复杂度和空间复杂度都为.

这种方法相对比较简单，具体实现代码就不赘述。

 

方法二：

        另外一个典型的求法就是利用欧拉算法，也就是说，要利用gcd(A, B) = gcd(A-B, B)这一步的特性。假设A>B的情况，那么可以多次采用gcd(A, B) = gcd(A-B, B)这一规则，然后直到一方的数字减少到0.那么最后剩下的另外一个数就是我们要求的最大公约数。

        前面提出这么个步骤还有一定的优化的地方。假设A>B,经过若干次的运算后，使得A-NB < B，此时，不等式左边的结果值相当于A mod B。也就是说，gcd(A, B) = gcd(A mod B, B) = gcd(B, A mod B). 那么，根据前面的这种推导关系，我们可以得出如下的一个实现方法：

 

public static long gcd(long a, long b)
{
	if(b == 0)
		return a;
	else
		return gcd(b, a % b);
}

 前面数学的定义就形成了一个很好的递归关系。如果我们想将前面的递归实现转换成非递归的实现的话，需要考虑的就是每次两个数字都要将与对方求模的结果赋给自己，然后比较结果是否为0，如果是则返回另外一个数字。

非递归版本的实现代码如下：

 

public static long gcdIter(long a, long b)
{
	if(b == 0)
		return a;
	while(true)
	{
		a = a % b;
		if(a == 0)
			return b;
		b = b % a;
		if(b == 0)
			return a;
	}
}

    还有另外一个版本的写法，这个思路用python实现看起来比较简洁，这里就一并贴出来了。最重要的是这部分代码能够考虑到各种特殊的情况：

 

def gcd(p, q):
    while p != q:
        if p < q:
            p, q = q, p
        if q == 0:
            return p
        p, q = q, p % q
    return p

if __name__ == '__main__':
    print gcd(0, 0)
    print gcd(1, 0)
    print gcd(0, 1)
    print gcd(2, 4)
    print gcd(3, 5)

 

最小公倍数：

        前面费老劲终于整出了最大公约数的求法，那么慢着，最小公倍数该怎么求呢？实际上，通过一条有意思的数学性质，就可以通过最大公约数来求出最小公倍数来。假设用LCM(A, B)来表示最小公倍数，GCD(A, B)表示最大公约数。那么就有这样的性质：LCM(A, B) * GCD(A, B) = AB。所以说，只要求出GCD(A, B)，在用AB的结果除以最大公约数，得到的结果就是最小公约数了。呵呵，这是一个比较取巧的地方。

 

总结

        求最大公约数和最小公倍数主要在一些数学的问题中用到，利用欧拉算法的一个改进就可以达到log(N)这个时间复杂度的计算方法。再利用他们的乘积关系，也可以很方便的求出最小公倍数来。具体欧拉算法的证明以及这个数学乘积关系的证明后面补上。:)

 

参考资料

data structures and problem solving using java