C++输入两个正整数，用辗转相除法计算它们的最大公约数

好的，以下是C++代码实现：

#include <iostream>

using namespace std;

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

int main() {
    int a, b;
    cout << "请输入两个正整数：";
    cin >> a >> b;
    int result = gcd(a, b);
    cout << "最大公约数为：" << result << endl;
    return 0;
}

以上代码中，我们定义了一个 `gcd` 函数，用于计算两个正整数的最大公约数。主函数中，我们首先输入两个正整数，然后调用 `gcd` 函数计算它们的最大公约数并输出结果。

相关问题

设计一个c++程序，程序功能：输入两个正整数，用辗转相除法计算它们的最大公约数

以下是使用辗转相除法计算两个正整数的最大公约数的C程序：

#include <stdio.h>

int main()
{
    int num1, num2, remainder, gcd;

    printf("请输入两个正整数：\n");
    scanf("%d %d", &num1, &num2);

    while (num2 != 0)
    {
        remainder = num1 % num2;
        num1 = num2;
        num2 = remainder;
    }

    gcd = num1;

    printf("最大公约数为：%d\n", gcd);

    return 0;
}

运行结果：

请输入两个正整数：
24 36
最大公约数为：12

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