辗转相除法-求最大公因数

辗转相除法是一种求最大公因数的计算方法。

这种方法在编程中很常用，在数学计算中也可以用来求很复杂的最大公因数问题。

如何使用#

题目：求最大公因数(36,14)

我们如何用辗转相除法做这道题呢？

{ 反复用除数除以余数直到除尽 \\\\ 36{\div}14=2\dots8\\ 14{\div}8=1\dots6\\ 8{\div}6=1\dots2\\ 6{\div}2=3\\ 最后一个除数就是最大公约数，也就是2 }

我们算出最大公约数(36,14)=2

到这里，我们就知道如何使用辗转相除法了。

但是，鲁迅曾说过“我们学公式必须得懂得原理”，我们明白了原理才能灵活运用

求最大公因数(a,b)

首先我们推出这几条式子

{ a{\div}b=q\dots r \\ a=bq+r \\ r=a-bq }

这是我们辗转法的原理

(a,b)=(b,r) \\a和b的最大公约数就等于b和r的最大公约数 }

接下来让我们证明这条公式

{ (1)设(a,b)=d \\那么a=dm,b=dn \\然后我们将其带入r=a-bq \\ 得r=d(m-nq)\\ 因为m,n,q都是整数，所以r是d的倍数，d是r的因数\\ 所以：只要是a,b的因数，就一定是d,r的约数\\ }

{ (2)设(b,r)=d\\ 和之前一样，那么b=dx,r=dy\\ 然后将其代入a=bq+r\\ 得a=d(xq+y)\\ 因为x,q,y都是整数，所以a是d的倍数，d是a的因数\\ 所以：只要是d,r的因数，就一定是a的因数\\ }

这样，我们就得出(a,b)的因数和(b,r)的因数相同，它们的因数都相同，那么它们的最大公因数也就相同。

所以我们要求(a,b)的最大公因数，我们就通过可以求(b,r)的最大公因数来得到。

现在我们再来看看开头的题

题目：求最大公因数(36,14)

反复用(a,b)=(b,r)的方法

(36,14)=(14,8)=(8,6)=(6,2)

最后得到(6,2)，显而易见最大公约数是2

接下来看看我们如何在C++中用辗转相除法写gcd函数

gcd函数就是用来求最大公因数的函数

1
int gcd(int a,int b) {
2
  while (a % b != 0) //a能被b整除时就终止循环
3
    {
4
    int r = a % b;
5
    a = b;
6
    b = r; //讲a换成除数b，b换成余数r
7
  }

当然也可以直接用algorithm头文件中的gcd函数，

我们学会自己写是为了理解原理，提升思维，

自己写还可以在有特殊需求的时候更自定义化。