辗转相除法--最大公约数/最大公倍数

什么是辗转相除法？

  辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。最早出现在公元前300年古希腊著名数学家欧几里得的《几何原本》》(第VII卷,命题i和ii)中。而在中国则可以追溯至东汉出现的《九章算术》。而在现代数学中，应该是属于数论的部分的。
  它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止，最后的除数就是这两个数的最大公约数，用这数除这两个数的乘积就是这两个数的最大公倍数。
非递归实现方法：

int gcd(int a, int b) {int r;while(r = a%b){a = b;b = r;}return b;}

递归实现方法：

//要求ｘ＞ｙ int gcd(int x,int y){return (!y)?x:gcd(y,x%y); }

总结

以上是生活随笔为你收集整理的辗转相除法--最大公约数/最大公倍数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。