深圳低价做网站/百度广告投放平台官网

转：蓝魔之泪de万事屋百度博客

http://hi.baidu.com/didihl/blog/item/533b1fec7cea252063d09f82.html

辗转相除算法的简介

在数论中，辗转相除法(国际上一般称为Euclidean Algorithm 或

Euclid's Algorithm，即欧几里得算法)是一种求任意两个欧几里得环(Euclidean

Domain)中的单位(如：整数)的最大公约数的算法。这个算法的一个重要特点就是其不需要通过分解因式来求取最大公约数。辗转相除法正因为其易操作性与易实现性而成为了计算机编程中的一个重要的求最大公约数的常用算法。

辗转相除法的过程描述与应用

给出两个自然数 a和 b：检查 b 是否为0；如果是，则 a 为最大公约数。如果不是，则分别用 b 和 a除 b 的余数作为上一步中的a和b 重复这一检查步骤。

正如上面所提到的，辗转相除法是编程中求最大公约数的常用算法，那么下面就是一个C++中通过递归实现辗转相除法的程序段范例：

int gcd (int v1, int v2)

{

return ( b == 0 ？a ：gcd(b，a % b

)；

}

注：过程名设为 gcd 是为了更明显的标明这段程序的意图。因为 gcd是 greatest

common

divisor(最大公约数)的缩写。再编写辗转相除法求最大公约数的过程是，最好将其命名为 gcd以方便他人日后阅读。

辗转相除法的证明

设两数为a、b(b＜a)，求它们最大公约数的步骤如下：用b除a，得a＝bq＋r(0≤r＜b)(q是这个除法的商)。若r=0,则b是a和b的最大公约数。若r≠0,则继续考虑。

首先，应该明白的一点是任何 a 和 b 的公约数都是 r

的公约数。要想证明这一点，就要考虑把 r 写成 r=a-bq。现在，如果 a 和 b 有一个公约数 d，而且设 a=sd ,

b=td, 那么 r = sd-tdq = (s-tq)d。因为这个式子中，所有的数(包括 s-tq )都为整数，所以 r 可以被 d

整除。

对于所有的 d 的值，这都是正确的；所以 a 和 b 的最大公约数也是 b 和 r

的最大公约数。因此我们可以继续对 b 和 r 进行上述取余的运算。这个过程在有限的重复后，可以最终得到 r=0 的结果，我们也就得到了

a 和 b 的最大公约数。

此法不完备：还需

第四步：可以断定m-kn与n互素【否则，可设m-kn=xd，n=yd，(d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c】

最大公倍数：x*y/r

参考资料：

3.http://hi.baidu.com/didihl/blog/item/533b1fec7cea252063d09f82.html

4.百度百科：http://baike.baidu.com/view/255668.htm#2