C++求两数最大公约数穷举法

在C++中，利用穷举法（也称为辗转相除法或欧几里得算法）来求两个整数的最大公约数（GCD，Greatest Common Divisor）是一种经典的方法。这种方法基于这样的数学原理：对于任意两个正整数a和b（假设a >= b），它们的最大公约数等于较小的数和两数相除余数的最大公约数。

以下是用C++实现穷举法求GCD的基本步骤：

#include <iostream>

int gcd(int a, int b) {
    // 当b为0时，a就是最大公约数
    if (b == 0)
        return a;
    else
        // 否则，继续将b替换为a除以b的余数，直到余数为0
        return gcd(b, a % b);
}

int main() {
    int num1, num2;
    std::cout << "请输入两个整数: ";
    std::cin >> num1 >> num2;
    std::cout << "这两个数的最大公约数是: " << gcd(num1, num2);
    return 0;
}

在这个程序中，`gcd`函数是一个递归函数，当输入的第二个数为0时结束递归，返回第一个数作为结果。

相关问题

C++求两数最大公约数穷举法for循环

在C++中，使用穷举法（也称为辗转相除法或欧几里得算法）来求两个整数的最大公约数（Greatest Common Divisor, GCD），通常会通过嵌套的for循环来实现。这种方法的基本思想是利用较小数除以较大数的余数，然后用上一步得到的除数去除余数，如此反复直到余数为0，此时的除数即为最大公约数。以下是简单的示例代码：

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) { // 较小数为0的情况，大数就是GCD
        return a;
    } else { // 一般情况，穷举计算
        for (int i = 1; i <= b; ++i) {
            if (a % i == 0 && b % i == 0) {
                return i; // 如果同时能被a和b整除，那么i就是GCD
            }
        }
    }
}

int main() {
    int num1, num2;
    cout << "请输入两个整数：";
    cin >> num1 >> num2;
    cout << "它们的最大公约数是：" << gcd(num1, num2);
    return 0;
}

穷举法求最大公约数C++

以下是C++中使用穷举法求最大公约数的代码示例：

#include <iostream>
using namespace std;

int main() {
    int a, b, tem, gcd;
    cout << "请输入两个正整数：" << endl;
    cin >> a >> b;
    if (a < b) { // 交换a和b的值，使a大于b
        tem = a;
        a = b;
        b = tem;
    }
    for (int i = 1; i <= b; i++) { // 从1到b逐个判断是否为a和b的公约数
        if (a % i == 0 && b % i == 0) {
            gcd = i; // 如果是公约数，则更新最大公约数
        }
    }
    cout << "这两个数的最大公约数为：" << gcd << endl;
    return 0;
}