greatest common divisor
又称辗转相除法
算法描述：给定两个正整数m和n，求他们的最大公因子，即能够同时整除m和n的最大正整数。
算法步骤：
若m<n，那么m?n，为了确保m>n。求m除以n得到的余数r。若r为0，算法结束，n为答案。若r不为0，则m←n，n←r，再跳转到步骤2。
其中←为赋值符号，右边的值赋值给左边；??为交换符号，两个变量交换它们的值。
算法正确性证明：
在经过步骤1，2之后，m，n，r满足下列关系：
m=qn+r
其中q是使等式成立的一个整数。比如42=2*20+2。
如果r=0，那么m是n的倍数，所以n是m和n的最大公因子；如果r≠0，那么整除m和n的任何数也一定整除r=m-qn(可以想象假设某个公因子是e，那么e的整数倍减去e的整数倍，得到的结果还是e的整数倍)，所以{m，n}和{n，r}的公因子集合是一样的。所以m←n，n←r是合理的，又因为r是m除以n的余数，所以r<n，那么算法是收敛的。
算法实现（python）：
m=int(input(“Please input a number m”))n=int(input(“Please input a number n”))#step 1if m<n: _t=m m=n n=_tdef gcd(m,n): #step 2 _r=m % n #step 3 if _r==0: return n #step 4 else: m=n n=_r return gcd(m,n)if __name__==”__main__”: print(gcd(m,n))
现在已经有了实现求最大公约数的算法，只需要稍微修改一下就可以求最小公倍数（Least Common Multiple）了。因为假设m和n的最大公约数是r，用字母c表示最小公倍数，就有：
代码如下：
def lcm(m,n): return int(m*n/gcd(m,n))
参考文献：
计算机程序设计艺术（美国高防vpsThe Art of Computer Programming），作者Donald Knuth
