最大公约数C++辗转相除法

辗转相除法，也称欧几里得算法，是求两个数最大公约数的常用方法。假设需要求两个正整数a和b的最大公约数，用辗转相除法的步骤如下：

1. 用a除以b，得到余数r；
2. 若r为0，则b即为最大公约数；
3. 若r不为0，则用b除以r所得的余数再除以r，如此循环，直到余数为0为止，此时最后的除数即为最大公约数。

下面是C++实现：

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

时间复杂度为O(logn)。

相关问题

C++辗转相除法求最大公约数

C语言中，使用辗转相除法求最大公约数的方法有两种实现方式。一种是递归实现，另一种是循环实现。

递归实现的代码如下：

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

循环实现的代码如下：

int gcd(int a, int b) {
    if (b > a)
        return gcd(b, a);
    int remind = 1;
    while (remind) {
        remind = a % b;
        a = b;
        b = remind;
    }
    return a;
}

这两种方法的原理都是通过辗转相除的过程，即用较大的数除以较小的数得到余数，再用较小的数除以余数以此循环，直到最后余数为零。最后一次除的数即为最大公约数。

所以通过调用这两个方法，可以求出两个正整数的最大公约数。

c++辗转相除法求最大公约数

以下是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 = 12, b = 18;
    cout << "The GCD of " << a << " and " << b << " is " << gcd(a, b) << endl;
    return 0;
}

在上面的代码中，我们定义了一个名为`gcd`的函数，该函数使用递归的方式实现了辗转相除法。在主函数中，我们定义了两个整型变量`a`和`b`，并将它们的值分别设置为12和18。然后，我们调用`gcd`函数来计算它们的最大公约数，并将结果输出到控制台。