java递归实现最大公约数和最小公倍数

本文主要是介绍java递归实现最大公约数和最小公倍数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一个最大公约数使用的2300年前被发明的欧几里得算法求得，大致原理为:

如果有两个非负整数p、q，若q==0,则最大公约数为p；否则,p和q的最大公约数就是p除以q所得的余数和q的最大公约数。

第二个最小公倍数更简单

如果有两个非负整数p、q，若q==0,则最大公约数为p；否则,p和q的最大公约数就是p除以q所得的余数和q的最大公约数。

关键代码如下：

//最大公约数(Greatest Common Divisor)
public int gcd(int p,int q){if(q == 0)    return p;return gcd(q, p % q);}//最小公倍数(Least Common Multiple)　
public int lcm(int p,int q){int pq = p * q;return pq / gcd(p,q);}

这篇关于java递归实现最大公约数和最小公倍数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---