求最大公约数

求两个整数的最大公约数，最经典的做法是利用辗转相除法：不断用较小数去除较大数，并用余数替代被除数，直到余数为 0，此时的除数就是最大公约数。

C 语言实现

int gcd(int x,int y)
{
	int temp=0;
	while(y)
	{
	    temp=y;
	    y=x%y;
	    x=temp;
	}
	return x;
}

最小公倍数=x*y/gcd(x,y)

有了 gcd 之后，求最小公倍数就非常容易：两数乘积除以它们的最大公约数，即 x * y / gcd(x, y)。