最大公约数（辗转相除法）

发表于 更新于 分类于

辗转相除法，又称欧几里得算法，是求最大公约数(Greatest Common Divisor)的算法。

算法描述

设两数为$a$、$b$ $(a>b)$，求$a$和$b$最大公约数$gcd(a，b)$的步骤如下：

  1. 用$b$除$a$，得$a÷b=q…r(0\leq r)$。
  2. 若$r=0$，则$gcd(a,b)=b$；结束。
  3. 若$r≠0$，取$a=b,b=r$，执行第1步。

原理证明

设两数为$a$、$b$ $(b\leq a)$，用$gcd(a,b)$表示$a$，$b$的最大公约数，$r=a\ mod\ b $为$a$除以$b$以后的余数，$k$为$a$除以$b$的商，即$a÷b=k…r$。

辗转相除法即是要证明$gcd(a,b)=gcd(b,r)$。

  1. 令$c=gcd(a,b)$，则设$a=mc$，$b=nc$
  2. 则$r =a-kb=mc-knc=(m-kn)c$
  3. 即$c$也是$r$的因数
  4. 可以断定$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$，与前面结论矛盾】

从而可知$gcd(b,r)=c$，继而$gcd(a,b)=gcd(b,r)$。

算法实现(c++)

递归方式：

1
2
3
4
5
6
7
int gcd(int a,int b)
{
	if(b == 0)
    	return b;
    else
    	return gcd(b, a % b)
}

迭代方式：

1
2
3
4
5
6
7
8
9
10
int gcd(int a, int b)
{
    while(b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}