最大公约数（gcd）和最小公倍数（lcm）

xiufanivan · 2023-03-17 17:32:03 · 个人记录

先使用辗转相除法求出gcd，再利用性质：lcm(a, b) = \frac{ab}{gcd(a, b)}，求出lcm

代码：

#include <iostream>
#include<algorithm>

using namespace std;

// 欧几里得算法，辗转相除法 
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
} 

int main() {
    int n, m;
    cin >> n >> m;

    int GCD1 = gcd(n, m);
    cout << GCD1 << endl;  // 最大公约数
    cout << n / GCD1 * m << endl;  // 最小公倍数，这里先除再乘，避免n×m可能过大

    // 使用c++的algorithm库函数__gcd()，返回值为最大公约数 
    int GCD2 = __gcd(n, m);
    cout << GCD2 << endl;  // 最大公约数
    cout << n / GCD2 * m << endl;  // 最小公倍数

    return 0;
}