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

1.欧几里得算法原理

数学原理：

其中，

•  a 和 b 是两个正整数
• a mod b 是 a 除以 b 的余数

原理为：两个数的最大公约数等于其中较小的数和两数相除余数的最大公约数

2.欧几里得算法步骤

具体步骤：

1. 比较两个数 a 和 b ，假设 a  >  b
2. 计算 a 除以 b 的余数 r = a mod b.
3. 如果 r = 0,则 b 就是 a 和 b 的最大公约数。
4. 如果 r != 0,则 将 b 赋值给 a，将 r 赋值给 b ，然后重复步骤 2 和 3 。

3.举例 

假设我们要求GCD(48，18):

1. 48 mod 18 等价于 48 % 18 = 12 (两者余数为12).
2. 按照上面提到的步骤，现在计算GCD(18,12)。也就是求18 mod 12（18 % 12 = 6）
3. 现在计算GCD(12,6).12 mod 6 = 0;
4.  余数变成了0，所以GCD(48,18) = 6

4.实现代码

c++代码实现：

#include <iostream>
using namespace std;

// 计算两个数的最大公约数（非递归）
int gcd(int a, int b) {
    int r;
    while (b != 0) {
        r = a % b; // 计算余数
        a = b;         // 将 b 赋值给 a
        b = r;         // 将余数赋值给 b
    }
    return a; // 当 b 为 0 时，a 就是 GCD
}

// 递归计算两个数的最大公约数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

//上面两种都可以

int main() {
    int a, b;
    cin >> a >> b;
    int result = gcd(a, b);
    cout << "它们的最大公约数是: " << result << endl;
    return 0;
}

 5.直接使用函数

在c++中有一个函数__gcd(),直接计算两个数的最大公约数。这个函数定义在<algorithm>头文件中  （c++17版本以上可以使用（一般的做题平台都可以））

#include <iostream>
#include <algorithm> // 包含 __gcd() 函数的头文件
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int result = __gcd(a, b); // 使用 __gcd() 函数
    cout << "它们的最大公约数是: " << result << endl;
    return 0;
}