C++求最大公约数四种方法解析

在C++编程中，求最大公约数是一个基础而重要的问题。此处我们将介绍四种常见的求最大公约数的方法，包括暴力枚举法、更相减损法、辗转相除法、以及辗转相减法。

1. 暴力枚举法

暴力枚举法是一种最基础的求最大公约数的方法，其思路基于枚举法。具体来说，我们可以简单地从较小数开始逆序枚举每一个可能的公约数，直到找到两个整数均能整除的最大正整数。

下面是通过暴力枚举法求两个整数的最大公约数的C++程序：

#include <iostream>
using namespace std;

int gcd(int a, int b){
    int res = 1;
    for(int i = min(a, b); i >=1; i--){
        if(a % i == 0 && b % i == 0){
            res = i;
            break;
        }
    }
    return res;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << "The gcd of " << a << " and " << b << " is " << gcd(a, b) << endl;
    return 0;
}

我们输入两个正整数a和b，程序便会输出这两个正整数的最大公约数。

当然，暴力枚举法的时间复杂度比较高，而且枚举实际上只需要枚举到a和b中较小的数即可。因此，在接下来的方法中，我们会介绍更为高效的求最大公约数的方法。

2. 更相减损法

更相减损法是一种基于减法的方法，其思路基于两个整数a和b的差，并不断通过相减的方式将它们变为一个公因数与一个较小的数之间的差，直至两个数相等。具体来说，更相减损法可以写作：

int gcd(int a, int b){
    if(a == b) return a;
    if(a < b) swap(a, b);
    return gcd(a-b, b);
}

上述代码中，若a等于b，则返回a，若a小于b，则将a和b交换，然后将它们的差a-b与较小的数b作为新的a和b继续递归。当a等于b时，便找到了两个整数的最大公约数。

下面是更相减损法求两个整数的最大公约数的示例：

#include <iostream>
using namespace std;

int gcd(int a, int b){
    if(a == b) return a;
    if(a < b) swap(a, b);
    return gcd(a-b, b);
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << "The gcd of " << a << " and " << b << " is " << gcd(a, b) << endl;
    return 0;
}

3. 辗转相除法

辗转相除法也称为欧几里得算法，是一种基于除法的方法。其基本思路是，将两个整数a和b中较大的数除以较小的数得到一个余数c，然后将原来的较小的数b和余数c作为新的一对数，不断递归直至余数为0。此时，较小的数就是这两个数的最大公约数。

下面是辗转相除法求两个整数的最大公约数的示例：

#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, b;
    cin >> a >> b;
    cout << "The gcd of " << a << " and " << b << " is " << gcd(a, b) << endl;
    return 0;
}

4. 辗转相减法

辗转相减法与辗转相除法类似，其基本思路也是将两个整数不断相减的过程中取余数并递归，直至余数为0得到最大公约数。具体来说，辗转相减法可以写作：

int gcd(int a, int b){
    if(a == b) return a;
    if(a < b) swap(a, b);
    return gcd(a-b, b);
}

下面是辗转相减法求两个整数的最大公约数的示例：

#include <iostream>
using namespace std;

int gcd(int a, int b){
    if(a == b) return a;
    if(a < b) swap(a, b);
    return gcd(a-b, b);
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << "The gcd of " << a << " and " << b << " is " << gcd(a, b) << endl;
    return 0;
}

通过比较发现，辗转相减法与更相减损法实际上是一样的，只是在处理减法的方式上有所不同。

以上四种方法均可以求得两个整数的最大公约数，其中辗转相除法是最为高效和常用的方法。