01公倍数与公因数
# 01 公倍数与公因数
公倍数(common multiple)是指在两个或两个以上的自然数中,如果它们有相同的倍数,这些倍数就是它们的公倍数。公倍数中最小的,就称为这些整数的最小公倍数(lowest common multiple,lcm)
公因数,亦称公约数。它是一个能同时整除若干整数的整数 。如果一个整数同时是几个整数的因数,称这个整数为它们的公因数;公因数中最大的称为最大公因数 (greatest common divisor,gcd)
利用辗转相除法,计算公式为gcd(a,b) = gcd(b,a mod b)
我们可以很方便地求得两个数的最大公因数;将两个数相乘再除以最大公因数即可得到最小公倍数。
int gcd(int a, int b){
if(b==0){
return a;
}
return gcd(b, a % b);
}
int lcm(int a, int b){
int gcdRes = gcd(a,b);
return a*b / gcdRes;
}
上次更新: 2023/11/19, 12:55:48