c++辗转相除法求最小公倍数

以下是使用C++辗转相除法求最小公倍数的代码示例：

#include<iostream>
using namespace std;

int main() {
    int m, n;
    cout << "请输入两个正整数m和n：" << endl;
    cin >> m >> n;
    int a = m, b = n;
    while (n != 0) {
        int r = m % n;
        m = n;
        n = r;
    }
    int lcm = a * b / m;
    cout << "最小公倍数为：" << lcm << endl;
    return 0;
}

相关问题

辗转相除法求最小公倍数C + +

辗转相除法，也称为欧几里得算法，是一种古老的求两个整数最大公约数（Greatest Common Divisor, GCD）的方法，进而可以利用GCD来计算这两个数的最小公倍数（Least Common Multiple, LCM）。以下是C++实现辗转相除法的基本步骤：

// 定义函数计算GCD
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// 利用GCD计算LCM
int lcm(int a, int b) {
    return a * (b / gcd(a, b));
}

int main() {
    int num1, num2;
    cout << "请输入两个整数：";
    cin >> num1 >> num2;
    cout << "两数的最小公倍数是：" << lcm(num1, num2) << endl;
    return 0;
}

在这个程序中，我们首先递归地计算两个数的最大公约数，然后用第一个数乘以第二个数除以它们的最大公约数，就得到了最小公倍数。

c++辗转相除求最小公倍数

要求两个数的最小公倍数，可以先通过辗转相除法求出它们的最大公约数，然后用两数之积除以最大公约数即可得到最小公倍数。以下是C++的实现代码：

#include <iostream>

using namespace std;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

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

int main() {
    int a = 12, b = 18;
    cout << "最小公倍数为：" << lcm(a, b) << endl;
    return 0;
}

输出结果为：

最小公倍数为：36