GCD&LCM

GCD最大公约数

概念

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

求法

unsigned int gcd(unsigned int a,unsigned int b)
{
    while(b^=a^=b^=a%=b);//注意此处分号
    return a;
}

LCM最小公倍数

概念

几个数共有的倍数叫做这几个数的公倍数，其中除0以外最小的一个公倍数，叫做这几个数的最小公倍数。

求法

int LCM(int a,int b)
{
	int temp_lcm;
	 //最小公倍数等于两数之积除以最大公约数
	temp_lcm = a * b /GCD(a,b);
	return temp_lcm;
}