欧几里得算法求最小公倍数和最大公约数

一.最大公约数

gcd(a,b)=gcd(b,a%b) 递归式,当且仅当b=0，易得0和a的公约数为a.(可作为递归的出口)

证明：

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

 二.最小公倍数

给定整数a b，求a b的最小公倍数

有图可知

a和b 的最小公倍数等于a*b/gcd（a，b），两个数相乘等价于a，b所有因子相乘，但中间共同部分多乘了一次，多乘的部分为a和b的最大公约数

int gcd(int a, int b)
{if (b == 0) return a;else return gcd(b, a % b);
}
int main()
{int a = 6, b = 4;//最大公约数cout << gcd(a,b)<<endl;//最小公倍数cout << a * b / gcd(a, b);
}