GCD最大公约数——辗转相除法实现

由 glados 发布

一个比较简单的算法,这里记录一下相关笔记。

最大公约数是指能够整除多个整数的最大正整数(这里面多个整数不能都为0)例如6和4的最大公约数就是2,13和3的最大公约数是1。

算法实现

平时用的时候如果是C++,那么std库里面就已经有这个函数了,直接调用就行。具体可以看std::gcd的用法。比较常见的实现方式是:

int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}

这里采用的是辗转相除法,两数相除取余数和除数继续相除,直到余数为0,这时前一个余数就是最大公约数。举个例子:

252和105,求最大公约数:

首先第一步,$252 \mod 105 = 147$。下一步要用余数和除数继续相除,因为$147 > 105$所以$147$在下一步要继续当被除数。

第二步,$147 \mod 105 = 42$,得到余数$42$,因为$42$小于$105$,所以下一步需要$105$当被除数,$42$当除数。

第三步,$105 \mod 42 = 21 $,得到余数$21$。

最后一步,$42 \mod 21 = 0$,取上一步的余数$21$,就是最大公约数。

这里解释一下,实际上y充当的是求余之后的结果,当求余结果等于0的时候那么说明已经不需要继续递归下去了,直接取上一次求余的结果,就可以得到最大公约数,而刚好x存放的就是上一次传入的y(此时假设已经在递归中),即x%y,上一次求余的结果,因此在当前y为0时应当返回x

参考资料

  1. C++ 中的 std::gcd 函数
  2. 辗转相除法

暂无评论

发表评论