java最大公约数和最小公倍数

1. 最大公约数

1.1 概念

greatest common divisor(gcd)

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。

a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。

1.2 欧几里德算法

欧几里德算法又称辗转相除法， 用于计算两个整数a, b的最大公约数。其计算原理如下：

定理： gcd(a, b) = gcd(b, a mod b)

在 gcd(b, a mod b) 中，当 a mod b 等于0，此时b就是最大公约数。

比如：
gcd (6, 4) = gcd (4, 6%4) = gcd (4, 2) ->
gcd (4, 2) = gcd (2, 4%2) = gcd (2,0)
得出最大公约数为2.

1.3 java实现

publicintgcd(int x,int y){return y ==0? x :gcd(y, x % y);}

2. 最小公倍数

lowest common multiple (lcm)

2.1 解法

a,b的最大公约是 lcm (a, b)，因为：

a * b = lcm (a, b) * gcd (a, b)

没错，就是这样，Bingo！