最小公倍数(英语:least common multiple,lcm)是数论中的一个概念。若有一个数
,可以被另外两个数
、
整除,且
同时大于或等于
和
,则
为
和
的公倍数。
和
的公倍数有无限个,而所有正的公倍数中,最小的公倍数就叫做最小公倍数。同样地,若干个整数公有的倍数中最小的正整数称为它们的最小公倍数。
整数
的最小公倍数一般记作:
,或者参照英文记法记作
。
对分数进行加减运算时,要求两数的分母相同才能计算,故需要通分;标准的计算步骤是将两个分数的分母通分成它们的最小公倍数,然后将通分后的分子相加。
与最大公因数之关系
两个整数的最小公倍数与最大公因数之间有如下的关系:
![{\displaystyle \operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21b7802ef960fe4eb40b4c75e38b0ed9c58d2aa3)
计算方法
最小公倍数可以通过多种方法得到,最直接的方法是列举法,从小到大列举出其中一个数(如最大数)的倍数,当这个倍数也是另一个数的倍数时,就求得最小公倍数。另一个方法是利用公式
来求解,这时首先要知道它们的最大公因数。而最大公因数可以通过短除法得到。
利用整数的唯一分解定理,还可以用质因数分解法。将每个整数进行质因数分解。对每个质数,在质因数分解的表达式中寻找次数最高的乘幂,最后将所有这些质数乘幂相乘就可以得到最小公倍数。譬如求216、384和210的最小公倍数。对216、384和210来说:
,
,
。
- 其中
对应的最高次乘幂为
;
对应的最高次乘幂为
;
和
对应的最高次乘幂分别是
与
。将这些乘幂乘起来,就可以得到最小公倍数:
。
短除法
利用短除法,可以快速计算出多个整数的最小公倍数。
以下为例子:
假设我们要求12、20和42的最小公倍数。
a: 6 |12 18 42
b: 2 3 7
最小公倍数=a×b
因此,12、18和42和最小公倍数=6×2×3×7
所以,6×2×3×7=252,12、18和42的最小公倍数是252
递归计算多个整数的最小公倍数
可以递归求出多个整数的最小公倍数:欲求
,只需求
。
这利用了性质
。该性质证明如下:
记
的质因数分解分别为
,其中
是第
个质数。
那么根据最小公倍数的定义,
,
,
证毕。
程式代码
以下使用辗转相除法求得最大公因数,之后再求最小公倍数。
C
int GCD(int a, int b) {
if(b) while((a %= b) && (b %= a));
return a + b;
}
int LCM(int a, int b) {
return a * b / GCD(a, b);
}
C++
template<typename T>
T GCD(T a, T b) {
if (b) while((a %= b) && (b %= a));
return a + b;
}
template<typename T>
T LCM(T a, T b) {
return a * b / GCD(a, b);
}
C#
int GCD(int a, int b)
{
return a % b == 0 ? b : GCD(b, a % b);
}
int LCM(int a, int b)
{
return a * b / GCD(a, b);
}
Go
func GCD(a, b int) int {
if b == 0 {
return a
}
return GCD(b, a%b)
}
func LCM(a, b int) int {
return a * b / GCD(a, b)
}
Java
int GCD(int a, int b) {
return a % b == 0 ? b : GCD(b, a % b);
}
int LCM(int a, int b) {
return a * b / GCD(a, b);
}
Pascal
function gcd(a,b:integer):longint;
begin
if b=0 then gcd:=a
else gcd:=gcd(b,a mod b);
end;
function lcm(a,b:integer):longint;
begin
lcm:=(a*b) div gcd(a,b);
end;
Python
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
def lcm(a, b):
return a * b / gcd(a, b)
Ruby
def gcd(a, b)
b.zero? ? a : gcd(b, a % b)
end
def lcm(a, b)
a * b / gcd(a, b)
end
Swift
func gcd(_ a: Int, _ b: Int) -> Int {
return b == 0 ? a : gcd(b, a % b)
}
func lcm(_ a: Int, _ b: Int) -> Int {
return a * b / gcd(a, b)
}
应用
求最小公倍数是进行分数加减法时的步骤之一。将分母通分时,会把所有分数的分母通分为它们的最小公倍数,然后将分子相加。例如:
![{\displaystyle {2 \over 21}+{1 \over 6}={4 \over 42}+{7 \over 42}={11 \over 42}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed5503ea5b6cffd8cb14cd2819c64cc1e37791c5)
其中分母42就是21与6的最小公倍数。
参见
参考来源