2、输入两个正整数 m和n，求出它们的最大公约数和最小公倍数。 算法描述： （1）用辗转相除法求最大公约数+ m对n求余为a，若a不等于0，则 m-n，，n=a，继续求余，否则 n 为最大公约数， （2） 最小公倍数=两个数的积/最大公约数 c程序

为了计算两个正整数 `m` 和 `n` 的最大公约数（GCD，Greatest Common Divisor）和最小公倍数（LCM，Least Common Multiple），你可以使用以下步骤：

1. **辗转相除法求最大公约数**（欧几里得算法）：
- 初始化 a 为 n，b 为 m（因为我们要找的是 b 和 a 的 GCD，所以先用较大的作为 a）
- 当 b 不等于 0 时，将 a 赋值给 b，同时将 b 被 a 除后的余数赋值给 a
- 继续这个过程，直到 b 变为 0。此时，a 就是最大公约数。

int gcd(int m, int n) {
    if (n == 0)
        return m;
    else
        return gcd(n, m % n);
}

2. **计算最小公倍数**：
- 使用公式 LCM(a, b) = |a * b| / GCD(a, b)，其中 "|" 表示取绝对值。如果 m 和 n 都是非负数，那么可以直接用乘法计算，然后除以最大公约数；如果是负数，需要先取绝对值再计算。

int lcm(int m, int n) {
    int abs_m = m > 0 ? m : -m;
    int abs_n = n > 0 ? n : -n;
    return (abs_m * abs_n) / gcd(abs_m, abs_n);
}

相关问题

python求解两个整数的最大公约数的由多种算法 可以穷举法，也可以辗转相除或辗转相减法。 从键盘输入2个正整数m和n,求它们的最大公约数和最小公倍数 案例： 输入： 87 34 输出： 最大公约数是1，最小公倍数是295

在Python中，求解两个整数的最大公约数(GCD)可以使用多种方法，包括穷举法、辗转相除法（欧几里得算法）和辗转相减法。这里我会介绍辗转相除法，它是最常用且效率较高的方法。

辗转相除法（也叫欧几里得算法）的基本思想是：对于两个整数a和b（a > b），它们的最大公约数等于b和a除以b的余数c的最大公约数。如果余数为0，则b就是最大公约数；否则，继续将较大的数替换为较小的数，直到余数为0为止。

以下是使用辗转相除法计算最大公约数的Python代码示例：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 用户输入
m = int(input("请输入第一个正整数m: "))
n = int(input("请输入第二个正整数n: "))

# 计算最大公约数
gcd_value = gcd(m, n)

# 根据公式：最小公倍数 = |a * b| / GCD(a, b)，计算最小公倍数
lcm_value = abs(m * n) // gcd_value

print(f"最大公约数是{gcd_value}，最小公倍数是{lcm_value}")

运行这个程序，你可以按照例子中的提示输入87和34，它会输出这两个数字的最大公约数以及它们的最小公倍数。如果你有其他相关的编程问题，也可以随时问我哦！

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