辗转相除法（欧几里得算法）算是求最大公约数最简单高效的算法了，这几行代码用最简洁的方式写了这个算法，值得牢牢记住：
代码语言：javascript复制#include <cstdio>
//最大公约数
int Gcd(int a, int b)
{
return b == 0 ? a : Gcd(b, a%b);
}
//最小公倍数
int Lcm(int a, int b)
{
return a / Gcd(a, b) * b;
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
int gcd = Gcd(a, b);
printf("%d与%d的最大公约数为%dn", a, b, gcd);
int lcm = Lcm(a, b);
printf("%d与%d的最小公倍数为%dn", a, b, lcm);
return 0;
}既然采用了递归，自然会想到会不会栈溢出，有人证明出，Gcd函数的递归层数不会超过4.785lgN 1.6723（N = max（a，b））。
求最小公倍数可以用lcm = a*b / gcd，为了防止a*b过大溢出，常采用先除以最大公约数再乘以b的方式。
