最大公约数和最小公倍数的求法分析 简介 求最大公约数和最小公倍数可能是编程中最常见的几个基本问题了。因为他们的基本概念基本上很早的时候就知道了，对他们的求法和他们之间的关系都比较有意思。 基本的数学性质 先从最大公约数这一部分开始吧。从本身的概念来理解的话，就是说假设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). 那么，根据前面的这种推导关系，我们可以得出如下的一个实现方法： Java代码 public static long gcd(long a, long b) { if(b == 0) return a; else return gcd(b, a % b); } 前面数学的定义就形成了一个很好的递归关系。如果我们想将前面的递归实现转换成非递归的实现的话，需要考虑的就是每次两个数字都要将与对方求模的结果赋给自己，然后比较结果是否为0，如果是则返回另外一个数字。 非递归版本的实现代码如下： 1. 2. 3. 4. 5. 6. 7. Java代码 1. public static long gcdIter(long a, long b) 2. { 3. if(b == 0) 4. return a; 5. while(true) 6. { 7. a = a % b; 8. if(a == 0) 9. return b; 10. b = b % a; 11. if(b == 0) 12. return a; 13. } 14. } 还有另外一个版本的写法，这个思路用python实现看起来比较简洁，这里就一并贴出来了。最重要的是这部分代码能够考虑到各种特殊的情况： Python代码 1. def gcd(p, q): 2. while p != q: 3. if p < q: 4. p, q = q, p 5. if q == 0: 6. return p 7. p, q = q, p % q 8. return p 9. 10. if __name__ == '__main__': 11. print gcd(0, 0) 12. print gcd(1, 0) 13. print gcd(0, 1) 14. print gcd(2, 4) 15. print gcd(3, 5) 最小公倍数： 前面费老劲终于整出了最大公约数的求法，那么慢着，最小公倍数该怎么求呢？实际上，通过一条有意思的数学性质，就可以通过最大公约数来求出最小公倍数来。假设用LCM(A, B)来表示最小公倍数，GCD(A, B)表示最大公约数。那么就有这样的性质：LCM(A, B) * GCD(A, B) = AB。所以说，只要求出GCD(A, B)，在用AB的结果除以最大公约数，得到的结果就是最小公约数了。呵呵，这是一个比较取巧的地方。 总结 求最大公约数和最小公倍数主要在一些数学的问题中用到，利用欧拉算法的一个改进就可以达到log(N)这个时间复杂度的计算方法。再利用他们的乘积关系，也可以很方便的求出最小公倍数来。具体欧拉算法的证明以及这个数学乘积关系的证明后面补上。:) 本文来源：https://www.wddqw.com/doc/0cdb407bae02de80d4d8d15abe23482fb4da02ed.html