最大公约数和最小公倍数(gcd和lcm)

gcd:

简介:

1
辗转相除法，又名欧几里得算法，用于求两个数 a , b 的最大公约数(最大公因子)

使用过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
举个例子：
a=24，其因子有1、2、3、4、6、8、12、24
b=15，其因子有1、3、5、15
最大公约数gcd(a,b)=gcd(24,15)=3

过程如下
a = 24, b = 15
1) t = 24%15 = 9，a = 15,b = 9;
2) t = 15%9 = 6, a = 9, b = 6;
3) t= 9%6 =3, a = 6, b = 3;
4) t = 6%3 = 0, a = 3, b = 0;
b>0条件不满足，while循环停止。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
//朴素版
	public static int gcd1(int a, int b) {
		while (b > 0) {
			int temp = a % b;
			a = b;
			b = temp;
		}
		return a;
	}
//精炼版
	public static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}

lcm

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

1
a*b/gcd(a,b)

代码：

1
2
3
public static int lcm(int a,int b) {
	return a*b/gcd(a,b);
}