怎样快速算出30和45的最大公因数（看看古人是怎么求最大公因数的）

弱水三千，只需取一瓢饮，学习中国古代数学的算法案例：辗转相除法与更相减损术，学会了求最大公因数很方便！

(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法.

(2)辗转相除法的算法步骤

第一步，给定两个正整数m，n

第二步，计算m除以n所得的余数r

第三步，m＝n，n＝r

第四步，若r＝0，则m，n的最大公约数等于m；否则，返回 第二步

第一步，任意给定两个正整数，判断它们是否都是偶数.若是，用 2 约简；若不是，执行第二步.

第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.

解　方法一　(辗转相除法)

319÷261＝1(余58)，

261÷58＝4(余29)，

58÷29＝2(余0)，

所以319与261的最大公约数为29.

方法二　(更相减损术)

319－261＝58，

261－58＝203，

203－58＝145，

145－58＝87，

87－58＝29，

58－29＝29，

29－29＝0，

所以319与261的最大公约数是29.

我是【学一点数学】，欢迎评论、点赞或关注我私聊！分享高考提分策略，涨分秘籍，还有海量高考资源相送，都是一手资料，纯干货。

,