原题：最大公约数求法大全
小复习
上次介绍了辗转相除这一特殊的最大公约数的求法。 你还记得吗？
辗转相除
将大的数除以小的数，除以出现的馀数(第一馀数) (出现的馀数)第二馀数)除以第一馀数，重复直到最后的馀数变为0。 如果求两个数的最大公约数的话，最后的除数就是这两个数的最大公约数。
那么，今天就来总结一下最大公约数的求法吧。
总结最大公约数的求法
1、质因数分解法
想法：将各数分别分解为素因数，取出各数中的所有公开素因数并连乘，得到的乘积就是这些数的最大公约数。
例如，假设求出24和60的最大公约数。
步骤1 :分解24和60。
24=2X2X2X3
60=2X3X2X5
步骤2:24和60的最大公约数=24和60乘以共同的共同因子，即为2X2X3=12。
2、短除法
思路：用短除法求最大公约数。 首先，用这些数的公约数连续剔除，直到所有的商品互相提质。 然后，连接所有的除数，得到的乘积是这些数的最大公约数。
短除法的本质是素因数分解法，只是用短除法符号进行素因数分解。
示例：
十二的系数是一、二、三、四、六、十二。
十八的系数是一、二、三、六、九、十八。
12和18的公因数是1、2、3、6。
12和18的最大公约数是6。
3、更相损法
想法：
第一步：任意给出两个正整数； 判断它们是否都是偶数。 如果是2，约简； 如果不是，请执行步骤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、辗转相除
辗转相除在前面的文章中有详细介绍哦。
这么多求法你掌握了多少种~回搜狐，多看看吧
责任编辑：