用c++求两个数的最大公约数

以下是两种用C++求两个数的最大公约数的方法：

方法一：暴力法

#include <iostream>
using namespace std;

int main() {
    int m, n, gcd;
    cin >> m >> n;
    gcd = m > n ? n : m;
    while (gcd > 1 && (m % gcd != 0 || n % gcd != 0)) {
        gcd--;
    }
    cout << gcd << endl;
    return 0;
}

方法二：欧几里德算法（辗转相除法）

#include <iostream>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;    int r = m % n;
    while (r != 0) {
        m = n;
        n = r;
        r = m % n;
    }
    cout << "gcd=" << n << endl;
    return 0;
}

相关问题

c++求两个数最大公约数和最小公倍数 只能用分支和循环结构

在C++中，仅使用分支和循环结构来求两个数的最大公约数（GCD，Greatest Common Divisor）和最小公倍数（LCM，Least Common Multiple）通常会涉及欧几里得算法，这是最基础并且效率高的方法。这里是一个简单的示例：

**计算最大公约数（GCD）：**

#include <iostream>

// 辗转相除法（Euclidean Algorithm）
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int num1, num2;
    std::cout << "Enter two numbers: ";
    std::cin >> num1 >> num2;
    int result = gcd(num1, num2);
    std::cout << "The GCD of " << num1 << " and " << num2 << " is " << result << "\n";
    return 0;
}

**计算最小公倍数（LCM）：**
由于LCM可以通过 GCD 和两个数直接乘积得到（即 LCM(a, b) = |a * b| / GCD(a, b)），所以也可以通过循环结构实现：

int lcm(int a, int b) {
    return abs(a * b) / gcd(a, b);
}

int main() {
    int num1, num2;
    std::cout << "Enter two numbers: ";
    std::cin >> num1 >> num2;
    int lcm_value = lcm(num1, num2);
    std::cout << "The LCM of " << num1 << " and " << num2 << " is " << lcm_value << "\n";
    return 0;
}

c++输入两个数求两个数最大公约数和最小公倍数

好的，以下是一个简单的 C++ 程序，可以实现您的要求：

#include <iostream>

using namespace std;

// 求最大公约数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// 求最小公倍数
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int main() {
    int num1, num2;
    cout << "请输入两个正整数：" << endl;
    cin >> num1 >> num2;

    cout << num1 << "和" << num2 << "的最大公约数是：" << gcd(num1, num2) << endl;
    cout << num1 << "和" << num2 << "的最小公倍数是：" << lcm(num1, num2) << endl;

    return 0;
}

这个程序会要求用户输入两个正整数，然后利用辗转相除法求它们的最大公约数，再利用最大公约数求出它们的最小公倍数，最后输出结果。