辗转相除法求最大公约数

记录一下学到的快速求最大公约数的办法

原理#

辗转相除法，也叫欧几里得算法，是用于求两个正整数的最大公约数的一种高效算法。它基于这样一个原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

实现#

直接粘代码吧

def func(m, n):
    while n:
        m, n = n, m % n
    return m

具体解释如下：

函数定义：

   def func(m, n):

定义了一个名为 func 的函数，接受两个参数 m 和 n，这两个参数用于传入需要计算最大公约数的两个数。

循环部分：

   while n:
       m, n = n, m % n
   ```

这是一个 `while` 循环，只要 `n` 不为 0，就会一直执行循环体。在循环体中，通过语句 `m, n = n, m % n` 实现了辗转相除的核心操作。它将 `n` 的值赋给 `m`，将 `m` 除以 `n` 的余数赋给 `n`。这样每次循环都在更新 `m` 和 `n` 的值，逐步逼近最大公约数。

3. **返回结果**：
```python
   return m
   ```

当 `n` 最终变为 0 时，循环结束，此时的 `m` 就是 `m` 和 `n` 最初传入值的最大公约数，将其返回。

4. **调用函数并输出结果**：
```python
   m = 72
   n = 36
   print(f"{m} 和 {n} 的最大公约数是: {func(m, n)}")
   ```

定义了两个变量 `m` 和 `n`，分别赋值为 72 和 36，然后调用 `func` 函数计算它们的最大公约数，并使用格式化字符串输出结果。

在这个例子中，计算过程如下：

- 初始 `m = 72`，`n = 36`。
- 第一次循环：`m = 36`，`n = 72 % 36 = 0`。
- 此时 `n` 为 0，循环结束，函数返回 `m` 的值 36，所以 72 和 36 的最大公约数是 36。