最小公倍數

维基百科,自由的百科全书
跳转至: 导航搜索

最小公倍數数论中的一个概念。若有一個數X,可以被另外兩個數A、B整除,且X大於(或等于)A和B,則X為A和B的公倍數。A和B的公倍數有無限個,而所有的公倍數中,最小的公倍數就叫做最小公倍數。兩個整數公有的倍數称为它们的公倍数,其中最小的一個正整数称为它们两个的最小公倍数。同样地,若干个整数公有的倍数中最小的正整数称为它们的最小公倍数。n整数的最小公倍数一般记作:,或者参照英文记法记作,其中lcm是英语中“最小公倍数”一词(lowest common multiple)的首字母缩写。

例如,十天干和十二地支的混合稱为一个陰曆,干支循環回歸同一名稱的所需時間,就是1210的最小公倍數,即是60──一個「甲子」。

分數进行加減运算時,要求兩數的分母相同才能計算,故需要通分;标准的计算步骤是将兩個分數的分母通分成它们的最小公倍數,然后将通分后的分子相加。

与最大公因数之关系[编辑]

两个整数的最小公倍数与最大公因数之间有如下的关系:

计算方法[编辑]

最小公倍数可以通过多种方法得到,最直接的方法是列举法,从小到大列举出其中一个数(如最大數)的倍数,当这个倍数也是另一个数的倍数时,就求得最小公倍数。另一个方法是利用公式来求解,这时首先要知道它们的最大公因数。而最大公因数可以通过短除法得到。

利用整数的唯一分解定理,还可以用質因數分解法。将每个整数进行质因数分解。对每个质数,在质因数分解的表达式中寻找次数最高的乘幂,最后将所有这些质数乘幂相乘就可以得到最小公倍数。譬如求216384210的最小公倍數。对216384210来说:

其中对应的最高次乘幂为对应的最高次乘幂为对应的最高次乘幂分别是。将这些乘幂乘起来,就可以得到最小公倍数:

程式代碼[编辑]

以下使用輾轉相除法求得最大公因數,之後再求最小公倍數。

C#[编辑]

private int GCD(int a, int b) {
	if(b) while((a %= b) && (b %= a));
	return a + b;
}
private int LCM(int a, int b) {
	return a * b / GCD(a, b);
}

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);
}

PASCAL[编辑]

1
var a,b,ans:integer;
function gcd(a,b:integer):longint;
begin
    if b=0 then gcd:=a
    else gcd:=gcd(b,a mod b ) ;
end;
2
var a,b,ans:integer;
function lcm(a,b:integer):longint;
begin
    readln(a,b );
    ans:=(a*b) div gcd(a,b);
    write(ans);
end;

JAVA[编辑]

private int GCD(int a, int b) {
	return a % b == 0 ? b : GCD(b, a % b);
}
private int LCM(int a, int b) { 
	return a * b / GCD(a, b);
}

应用[编辑]

求最小公倍数是进行分数加减法时的步骤之一。将分母通分时,会把所有分数的分母通分为它们的最小公倍数,然后将分子相加。例如:

其中分母42就是216的最小公倍数。

参见[编辑]

参考来源[编辑]

  • 柯召,孙绮,孙琦. 《数论讲义》. 高等教育出版社. 2005. ISBN 753205473X. 
  • 阿尔伯特﹒H﹒贝勒著 谈祥柏译. 《数论妙趣:数学女王的盛情款待》. 上海教育出版社. 1998. ISBN 7040091909.