最大公约数与最小公倍数

---

title: GCD&LCM
date: 2017-03-09 22:10:59
tags:
categories:
---

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;
}