# 最小公倍數

（重定向自最小公倍数

## 与最大公因数之关系

${\displaystyle \operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}}$

## 计算方法

${\displaystyle 216=2^{3}\times 3^{3}}$ ${\displaystyle 384=2^{7}\times 3^{1}}$ ${\displaystyle 210=2^{1}\times 3^{1}\times 5^{1}\times 7^{1}}$

${\displaystyle [216,384,210]=2^{7}\times 3^{3}\times 5^{1}\times 7^{1}=120960}$

a: 6 |12 18 42

b: 2 3 7

### 递归计算多个整数的最小公倍数

${\displaystyle a_{1},a_{2},a_{3}}$  的质因数分解分别为${\displaystyle \prod _{i=1}^{n}p_{i}^{e_{1i}},\prod _{i=1}^{n}p_{i}^{e_{2i}},\prod _{i=1}^{n}p_{i}^{e_{3i}}}$ ，其中 ${\displaystyle p_{i}}$  是第 ${\displaystyle i}$  个质数。

${\displaystyle \operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2}),a_{3})=\operatorname {lcm} (\prod _{i=1}^{n}p_{i}^{\max(e_{1i},e_{2i})},a_{3})=\prod _{i=1}^{n}p_{i}^{\max(\max(e_{1i},e_{2i}),e_{3i})}=\prod _{i=1}^{n}p_{i}^{\max(e_{1i},e_{2i},e_{3i})}}$

## 程式代碼

### 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<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

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)


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


### 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}}$

## 參考來源

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