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;
}

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

相关问题

1)输入两个正整数m和n，求其最大公约数和最小公倍数。 要求:用辗转相除法和穷举算法来做

当然，我可以帮你介绍两种方法：辗转相除法（也称为欧几里得算法）和穷举算法。

**1. 辗转相除法 (Euclidean Algorithm)**:
这是最常用的方法，因为它的效率较高。我们可以定义两个正整数 `a` 和 `b` 的最大公约数（GCD）为 `gcd(a, b)`，满足以下性质：

- 如果 `b == 0`，那么 `gcd(a, b)` 就是 `a`；
- 否则，`gcd(a, b)` = `gcd(b, a % b)`。

下面是用 C++ 实现的代码：

#include <iostream>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

// 计算最小公倍数 (LCM)
int lcm(int m, int n) {
    return (m * n) / gcd(m, n);
}

int main() {
    int m, n;
    std::cout << "Enter two positive integers: ";
    std::cin >> m >> n;
    std::cout << "The GCD of " << m << " and " << n << " is: " << gcd(m, n) << "\n";
    std::cout << "The LCM of " << m << " and " << n << " is: " << lcm(m, n) << "\n";
    return 0;
}

**2. 穷举算法 (Brute Force)**:
这种方法比较直接，但效率较低，适用于较小范围内的整数。我们需要从1遍历到两数中的较大值，看哪些数同时能被两个数整除。下面是简单的穷举法实现：

#include <iostream>

// 穷举法计算最大公约数
int bruteForceGCD(int a, int b) {
    for (int i = 1; i <= std::max(a, b); ++i) {
        if (a % i == 0 && b % i == 0) {
            return i;
        }
    }
    return 0;
}

int main() {
    int m, n;
    std::cout << "Enter two positive integers: ";
    std::cin >> m >> n;

    // 穷举法计算LCM
    int lcm = std::max(m, n);
    for (int i = lcm; ; ++lcm) { // 迭代直到找到合适的小于等于两者乘积的数
        if (bruteForceGCD(lcm, m) == m && bruteForceGCD(lcm, n) == n) {
            break;
        }
    }

    std::cout << "The GCD of " << m << " and " << n << " is: " << bruteForceGCD(m, n) << "\n";
    std::cout << "The LCM of " << m << " and " << n << " is: " << lcm << "\n";
    return 0;
}