最小公倍数 最小公倍数是数论中的一个概念。若有一个数formula_1，可以被另外两个数formula_2、formula_3整除，且formula_1大于（或等于）formula_2和formula_3，则formula_1为formula_2和formula_3的公倍数。formula_2和formula_3的公倍数有无限个，而所有正的公倍数中，最小的公倍数就叫做最小公倍数。同样地，若干个整数公有的倍数中最小的正整数称为它们的最小公倍数。formula_12整数formula_13的最小公倍数一般记作：formula_14，或者参照英文记法记作formula_15，其中lcm是英语中“最小公倍数”一词（"least common multiple"）的首字母缩写。 对分数进行加减运算时，要求两数的分母相同才能计算，故需要-{zh-hans:通分; zh-hant:扩分;}-；标准的计算步骤是将两个分数的分母-{zh-hans:通分; zh-hant:扩分;}-成它们的最小公倍数，然后将-{zh-hans:通分; zh-hant:扩分;}-后的分子相加。 与最大公因数之关系. 两个整数的最小公倍数与最大公因数之间有如下的关系： formula_16 计算方法. 最小公倍数可以通过多种方法得到，最直接的方法是列举法，从小到大列举出其中一个数（如最大数）的倍数，当这个倍数也是另一个数的倍数时，就求得最小公倍数。另一个方法是利用公式formula_17来求解，这时首先要知道它们的最大公因数。而最大公因数可以通过短除法得到。 利用整数的唯一分解定理，还可以用质因数分解法。将每个整数进行质因数分解。对每个质数，在质因数分解的表达式中寻找次数最高的乘幂，最后将所有这些质数乘幂相乘就可以得到最小公倍数。譬如求216、384和210的最小公倍数。对216、384和210来说： formula_18，formula_19，formula_20。 其中formula_21对应的最高次乘幂为formula_22；formula_23对应的最高次乘幂为formula_24；formula_25和formula_26对应的最高次乘幂分别是formula_27与formula_28。将这些乘幂乘起来，就可以得到最小公倍数： formula_29。 短除法 利用短除法，可以快速计算出多个整数的最小公倍数。 以下为例子: 假设我们要求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 递归计算多个整数的最小公倍数. 可以递归求出多个整数的最小公倍数：欲求 formula_30，只需求 formula_31。 这利用了性质 formula_32。该性质证明如下： 记 formula_33 的质因数分解分别为formula_34，其中 formula_35 是第 formula_36 个质数。 那么根据最小公倍数的定义，formula_37， formula_38， 证毕。 程式代码. 以下使用辗转相除法求得最大公因数，之后再求最小公倍数。 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); 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 T GCD(T a, T b) { if (b) while((a %= b) && (b %= a)); return a + b; template T LCM(T a, T 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; 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); RUBY. def gcd(a, b) b.zero? ? a : gcd(b, a % b) end def lcm(a, b) a * b / 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) Golang. 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) Xcode. 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) 应用. 求最小公倍数是进行分数加减法时的步骤之一。将分母-{zh-hans:通分; zh-hant:扩分;}-时，会把所有分数的分母-{zh-hans:通分; zh-hant:扩分;}-为它们的最小公倍数，然后将分子相加。例如： formula_39 其中分母42就是21与6的最小公倍数。