最大公约数、最小公倍数

辗转相除法是用于求两个非负整数 a 、 b 的最大公约数(gcd、Greatest Common Divisor)的方法，其基本逻辑如下：
直到 时，就可得：

注意：

1. a 必须大于等于 b 。

C语言实现：

// a must geq than b.
int gcd(int a, int b)
{
	int mod = a % b;
	if(mod)
		return gcd(b, mod);
	else
		return b;
}
复制

或者：

// a must geq than b.
int gcd(int a, int b)
	return a % b ? gcd(b, a % b) : b;
复制

用小值乘最大公约数即可。

int lcm(int a, int b)
	return a > b ? b * gcd(a, b) : a * gcd(b, a);
复制