最小公倍数与最大公因数

1.求两个数最大公约数

欧几里得算法

public static int gcd(int x,int y){
	if(x>y){
		int tmp = x;
		x = y;
		y = tmp;
	}
	return x == 0 ? y : gcd(y%x,x);
}

2.求两个数最小公倍数

在求的最大公约数的基础上

//求a、b的最小公倍数
int lcm(int a, int b){
    return a*b/gcd(a, b);
}

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