⼩复习
上⼀次我们介绍了⼀种特殊的最⼤公约数求法，叫做辗转相除法。你还记得吗？ 辗转相除法
⽤较⼩数除较⼤数，再⽤出现的余数（第⼀余数）去除除数，再⽤出现的余数（第⼆余数）去除第⼀余数，如此反复，直到最后余数是0为⽌。如果是求两个数的最⼤公约数，那么最后的除数就是这两个数的最⼤公约数。
那么，今天我们就对最⼤公约数求法做⼀个总结噢。
我的特岗生活
最⼤公约数求法汇总
1、质因数分解法
思路：把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这⼏个数的最⼤公约数。
降冰片烯
举例：假设我们求24和60的最⼤公约数。
第⼀步：分解24和60。
cc200024=2X2X2X3
60=2X3X2X5
第⼆步：24和60的最⼤公约数=24和60共有的公因⼦相乘，即2X2X3=12。
2、短除法
思路：短除法求最⼤公约数，先⽤这⼏个数的公约数连续去除，⼀直除到所有的商互质为⽌，然后把所有的除数连乘起来，所得的积就是这⼏个数的最⼤公约数。
短除法的本质就是质因数分解法，只是将质因数分解⽤短除符号来进⾏。
举例：
12的因数有：1、2、3、4、6、12。
18的因数有：1、2、3、6、9、18。
12与18的公因数有：1、2、3、6。
12与18的最⼤公因数是6。
3、更相减损法
思路：
第⼀步：任意给定两个正整数；判断它们是否都是偶数。若是，则⽤2约简；若不是则执⾏第⼆步。
第⼀步：任意给定两个正整数；判断它们是否都是偶数。若是，则⽤2约简；若不是则执⾏第⼆步。
第⼆步：以较⼤的数减较⼩的数，接着把所得的差与较⼩的数⽐较，并以⼤数减⼩数。继续这个操作，直到所得的减数和差相等为⽌。
则第⼀步中约掉的若⼲个2与第⼆步中等数的乘积就是所求的最⼤公约数。
举例：
⽤更相减损术求98与63的最⼤公约数。
由于63不是偶数，把98和63以⼤数减⼩数，并辗转相减：
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
金都高尔夫艺墅14-7=7
所以，98和63的最⼤公约数等于7。美国在线时代华纳
代码实现：
4、辗转相除法
辗转相除法在之前的⽂章中有详细介绍噢！
辗转相除
这么多求法你掌握了⼏种呢~
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议