【动画笔记】辗转相除法——求最大公约数和最小公倍数

最近咱摸起了C语言，尝试着结合最近学的运筹学写个计算工具，途中遇到了一个需求：分数的约分。

• 分数约分怎样一步到位呢？答案便是找分母和分子的最大公约数。

• 那么怎么尽快算出最大公约数呢？网上查了一查，发现了一个算法：辗转相除法。

这篇笔记就简单而直观地记录一下这个算法。

这个词非常贴近分数中约分的方法，所谓最大公约数即是多个整数共有的约数中最大的一个，在约分的时候分子和分母同时除以最大公约数，能得到最简分数。

因为上面说的过程中进行的都是整除运算，所以最大公约数也称为最大公因数。

不妨说得更直接一点，公因数就是公约数。

关于最大公约数的定义有两点需要注意：

1. 公因数/公约数是针对整数而言的。

2. 一般规定最大公约数为正整数，也就是满足如下公式：

   

   要算带有负号的数值时，可以给其套上绝对值，再计算。

现实中在求多个整数的最大公约数时，可以把这些数的因数都列举出来找共有的因数，亦或可以使用短除法：

我觉得这些方法其实多少有些依赖我们以往的经验，比如看到36,405,72中有6,5,2，可能很快能想到公因数3。（感觉我大脑里此时枚举了所有可能的因数）

这个过程如果抽象成编程语言中的算法，具体以代码实现，大概就是一个循环+判断所有数除以因数是否余数都为0了，时间复杂度是O(n)，随着运算数值的增大，代码的执行次数也会线性增加。

为了优化时间复杂度，这个时候就到了这篇笔记的主角——辗转相除法了。

上面提到了求多个整数的最大公约数，在这之前得先看看针对两个整数的二元算法