[C++知识库]HJ108 求最小公倍数 （lcm gcd） C/C++

题目连接

主要思路

主要介绍一下辗转相除法求最大公约数，举个例子：

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
参考资料:辗转相除法

ab的最小公倍数乘以ab的最大公因数 = ab的乘积
即$$lcm(a,b)?gcd(a,b)=a?b$$，所以我们求出最大约数之后，用ab的乘积除以最大公约数即为最小公倍数。

代码中给了lcm，以及gcd的迭代与递归写法，细节详见代码。

#include <iostream>
#include <string>
#include <vector>

using namespace std;


/*
//最大公约数 ,辗转相除法
//（原来的除数做被除数，余数做新的除数，当余数为0时，
//当前除数为最大公约数）
int gcd(int a,int b) {//迭代写法
    int tmp;
    while(b) {
        tmp = a%b;
        a = b;
        b = tmp;
    }
    return a;
}
*/


/*
* 推理：a和b的乘积等于他们最大公约数和最小公倍数的乘积
* 即：gcd(a,b)*lcm(a,b) = a*b;
*/

//最大公约数
int gcd(int a,int b) {//递归
    return b==0 ? a : gcd(b,a%b);
}

//最小公倍数
int lcm(int a,int b) {
    //return a*b/gcd(a,b);//可能溢出
    return a/gcd(a,b)*b;//防止溢出，先做除法
}


int main() {
    int a,b;
    cin>>a>>b;
    cout<<lcm(a,b)<<endl;
    return 0;
}