穷举法求最大公约数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;
}

相关问题

c++语言用穷举法求最大公约数最小公倍数

使用穷举法求最大公约数最小公倍数的基本思路是从 1 到较小数中的最大数依次枚举，找到能同时整除两个数的最大数作为最大公约数，然后通过两个数的乘积除以最大公约数得到最小公倍数。下面是 C++ 代码实现：

#include <iostream>
using namespace std;

int main() {
    int a, b, max, min;
    cout << "请输入两个正整数：" << endl;
    cin >> a >> b;
    max = (a > b) ? a : b; // 取较大数
    min = (a < b) ? a : b; // 取较小数
    for (int i = min; i >= 1; i--) {
        if (max % i == 0 && min % i == 0) { // 找到最大公约数
            cout << "最大公约数为：" << i << endl;
            cout << "最小公倍数为：" << max * min / i << endl;
            break;
        }
    }
    return 0;
}

上面的代码中，我们首先输入两个正整数，然后通过三目运算符获取较大数和较小数。接着从较小数中的最大数开始逆序枚举，找到能同时整除两个数的最大数作为最大公约数，并通过两个数的乘积除以最大公约数得到最小公倍数。最后输出结果。

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时结束递归，返回第一个数作为结果。