欧几里德算法

当我们谈论最大公约数（GCD），我们在讨论两个整数之间的共同因子，也就是能够同时整除这两个整数的整数。最大公约数是指在所有这些共同因子中最大的那个。

欧几里德算法是一种用于计算两个整数的最大公约数的古老而有效的方法。它的基本原理是通过反复应用以下观察来找到最大公约数：

观察：如果 a 和 b 是两个整数，且 a > b，那么 a 和 b 的最大公约数等于 b 和 a % b 的最大公约数。

这个观察的意义在于，我们可以将原始问题不断缩小为更小的问题，直到其中一个数成为零。当一个数为零时，另一个数就是最大公约数。

欧几里德算法的步骤如下：

• 初始化：将两个整数 a 和 b 分别赋给 x 和 y，其中 x >= y。

• 循环：进入循环，只要 y 不等于零，就执行以下步骤：

• 将 y 赋值给 x。
  计算 x 除以 y 的余数，将结果赋值给 y。
  返回结果：当循环结束时，y 变成了零，而 x 就是最大公约数，返回 x。

func gcd(x, y int) int {
    for y != 0 {
        x, y = y, x%y
    }
    return x
}