欧几里德算法（辗转相除法）

欧几里德算法，也称辗转相除法，是求两个整数的最大公约数的一种简单而有效的方法。该算法的基本思想是利用整除的性质，通过一系列的除法运算，求出两个数的最大公约数。

具体来说，对于两个非负整数 a 和 b，我们可以进行如下的运算：

• 用 a 除以 b，得到商 q 和余数 r。

• 如果余数 r 等于 0，则 b 就是最大公约数。

• 如果余数 r 不等于 0，则将 b 赋值为 r，然后继续进行第一步的运算。

上述运算重复进行，直到余数为 0，此时的 b 就是 a 和 b 的最大公约数。

例如，我们要求 36 和 24 的最大公约数。首先，我们用 36 除以 24，得到商 1 和余数 12。接着，我们用 24 除以 12，得到商 2 和余数 0。因为余数为 0，所以最大公约数为 12。

欧几里德算法具有计算简单、效率高的优点，因此在数论中被广泛地应用。同时，该算法也为其他数学领域提供了基础，例如代数、几何等。

以下是使用 C++ 实现欧几里德算法的代码：

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int a = 36, b = 24;
    cout << "gcd(" << a << ", " << b << ") = " << gcd(a, b) << endl;
    return 0;
}

代码中的 gcd 函数接受两个整数 a 和 b，返回它们的最大公约数。函数中使用递归的方式实现了欧几里德算法。在主函数中，我们调用 gcd 函数来计算 36 和 24 的最大公约数，并将结果输出到控制台上。输出结果为：

gcd(36, 24) = 12

从输出结果可以看出，36 和 24 的最大公约数为 12，与前面我们手算的结果一致。

需要注意的是，欧几里德算法的时间复杂度与输入数据的大小有关，具体来说是 O(log n)，其中 n 是输入的较大的整数。因此，该算法适用于计算较大整数的最大公约数。