最小公倍數
最小公倍數(英語:least common multiple,lcm)是數論中的一個概念。若有一個數,可以被另外兩個數、整除,且同時大於或等於和,則為和的公倍數。和的公倍數有無限個,而所有正的公倍數中,最小的公倍數就叫做最小公倍數。同樣地,若干個整數公有的倍數中最小的正整數稱為它們的最小公倍數。整數的最小公倍數一般記作:,或者參照英文記法記作。
對分數進行加減運算時,要求兩數的分母相同才能計算,故需要擴分;標準的計算步驟是將兩個分數的分母擴分成它們的最小公倍數,然後將擴分後的分子相加。
與最大公因數之關係
編輯計算方法
編輯最小公倍數可以通過多種方法得到,最直接的方法是列舉法,從小到大列舉出其中一個數(如最大數)的倍數,當這個倍數也是另一個數的倍數時,就求得最小公倍數。另一個方法是利用公式 來求解,這時首先要知道它們的最大公因數。而最大公因數可以通過短除法得到。
利用整數的唯一分解定理,還可以用質因數分解法。將每個整數進行質因數分解。對每個質數,在質因數分解的表達式中尋找次數最高的乘冪,最後將所有這些質數乘冪相乘就可以得到最小公倍數。譬如求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)
}
應用
編輯求最小公倍數是進行分數加減法時的步驟之一。將分母擴分時,會把所有分數的分母擴分為它們的最小公倍數,然後將分子相加。例如:
其中分母42就是21與6的最小公倍數。
參見
編輯參考來源
編輯- 柯召,孫綺,孫琦. 《数论讲义》. 高等教育出版社. 2005. ISBN 753205473X.
- 阿爾伯特·H·貝勒著 談祥柏譯. 《数论妙趣:数学女王的盛情款待》. 上海教育出版社. 1998. ISBN 7040091909.