辗转相除法求最大公约数的原理是什么












//最小公倍数=两数乘积/最大公约数






* 此时并不区分n1与n2的大小虽然求解过程是按照n2<n1来计算的,



* 相当于把值交换了有相当于求(大值,小值)因此需要讨论n1与n2的大小





两个整數的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的相除餘数的最大公约数


· TA获得超过3.5万个赞

如果两个数有朂大公约数A那么这两个数,以及这两个数的差还有大数除以小数的余数,必然都是A的倍数

所以当最后两个数刚好能整除时,较小的數就是最大公约数

你对这个回答的评价是?

下载百度知道APP抢鲜体验

使用百度知道APP,立即抢鲜体验你的手机镜头里或许有别人想知道嘚答案。

我要回帖

 

随机推荐