最小公倍数与最大公约数求法

一 求两个数的最大公约数GCD，使用欧几里德算法

//gcd(a,b)=gcd(a,a Mod b)
int gcd(int a,int b)
{
  if(a==0) return a;
  else return gcd(a,a%b);
}

二 求n个数的最小公约数

int gcd(int *a,int n)
{
   if(n==1) return *a;
   else return gcd(a[n-1],n%gcd(a[n],n-1));
}

求两个数的最小公倍数lcm

//求两个数的最小公倍数，即m*n除以最大公约数
int lcm(int m,int n)
{
   return m*n/gcd(m,n);
}