转：最大公约数算法很无聊吗？一个轻松方法（辗转相除法）3行代码搞定

最大公约数算法不是很无聊，计算最大公约数是数学中一个重要的概念，可以用于判断两个数是否互质、求分数的约分等，在很多领域都有广泛的应用。具体如下：

1. 判断两个数是否互质：两个数的最大公约数为1，说明这两个数是互质的。
2. 求分数的约分：将分子和分母的最大公约数约分掉，使得分数的值不变。
3. 求同余方程的最小正整数解：例如求ax ≡ b (mod m) 的最小正整数解。
4. 求两个数的最小公倍数：两个数的乘积除以它们的最大公约数。
5. 判断数的因数：通过求数的最大公约数判断是否为该数的因数。
   辗转相除法：
   • 如果两个整数不相等，则将大数除以小数，将余数代替较小数再进行同样的除法操作。
   • 重复上述操作，直到两个数相等，则两个数的最大公约数就是这两个数。
   更相减损术：
   • 将两个数中的较大数减去较小数，再把差代替较大数，进行同样的减法操作。
   • 重复上述操作，直到两个数相等，则两个数的最大公约数就是这两个数。
   穷举法：
   • 从1到较小数遍历，判断是否是两个数的公因数，如果是则记录。
   • 得到的公因数中，最大的即为两个数的最大公约数。
   质因数分解法：
   • 将两个数的质因数分解，并列出它们的公因数。
   • 公因数中的最大值即为两个数的最大公约数。
   下面是最大公约数算法的 Python 代码示例：
   def gcd(a, b):
   while b:
   a, b = b, a % b
   return a
   这是一种辗转相除法求最大公约数的方法，它每次通过计算余数，来降低计算复杂度。
   本文转载自https://www.vipshare.com/archives/40243