Question

如何快速求出两个数的所有公因数

如何快速求出两个数的所有公因数

Answer 1

• 小数还可以很快地看出来，大数怎么办？ 例如42和54

• 答：将每个数都用质数的乘积表示，选取里面相同质数的较小次方乘起来就OK了。 如42=2*3*7 54=2*3*9 所以（42，54）=2*3=6 那就不用次方表示呗，全乘出来写，选相同的个数少的 再如360=2*2*2*3*3*5 

Answer 2

这个没有快速的方法，速度快了容易出错。

Answer 3

01 观察法

运用能被2、3、5整除的数的特征进行观察。

例如，求225和105的最大公因数。因为225、105都能被3和5整除，所以225和105至少含有公因数（3×5）15。因为225÷15＝15，105÷15＝7，15与7互质，所以225和105的最大公因数是15。

02 查找因数法

先分别找出每个数的所有因数，再从两个数的因数中找出公有的因数，其中最大的一个就是最大公因数。

例如，求12和30的最大公因数。

12的因数有：1、2、3、4、6、12；

30的因数有：1、2、3、5、6、10、15、30。

12和30的公因数有：1、2、3、6，其中6就是12和30的最大公因数。

03 分解因式法

先分别把两个数分解质因数，再找出它们全部公有的质因数，然后把这些公有质因数相乘，得到的积就是这两个数的最大公因数。

例如：求125和300的最大公因数。因为125＝5×5×5，300＝2×2×3×5×5，所以125和300的最大公因数是5×5＝25。

04 关系判断法

当两个数关系特殊时，可直接判断两个数的最大公因数。例如，两个数互质时，它们的最大公因数就是这两个数的乘积；两个数成倍数关系时，它们的最大公因数就是其中较小的那个数。

05 短除法

为了简便，将两个数的分解过程用同一个短除法来表示，那么最大公因数就是所有除数的乘积。

例如：求180和324的最大公因数。

因为：5和9互质，所以180和324的最大公因数是4×9＝36。

06 除法法

当两个数中较小的数是质数时，可采用除法求解．即用较大的数除以较小的数，如果能够整除，则较小的数是这两个数的最大公因数。

例如：求19和152，13和273的最大公因数。因为152÷19＝8，273÷13＝21（19和13都是质数），所以19和152的最大公因数是19，13和273的最大公因数是13。

07 缩倍法

如果两个数没有之间没有倍数关系，可以把较小的数依次除以2、3、4……直到求得的商是较大数的因数为止，这时的商就是两个数的最大公因数。例如：求30和24的最大公因数。24÷4＝6，6是30的因数，所以30和24的最大公因数是6。

08 求差判定法

如果两个数相差不大，可以用大数减去小数，所得的差与小数的最大公因数就是原来两个数的最大公因数。例如：求78和60的最大公因数。78－60＝18，18和60的最大公因数是6，所以78和60的最大公因数是6。

　　

如果两个数相差较大，可以用大数减去小数的若干倍，一直减到差比小数小为止，差和小数的最大公因数就是原来两数的最大公因数。例如：求92和16的最大公因数。92－16＝76，76－16＝60，60－16＝44，44－16＝28，28－16＝12，12和16的最大公因数是4，所以92和16的最大公因数就是4。

09 辗转相除法

我们在求两个数的最大公约数时，通常的方法是短除，或者分别对两个数分解质因数，但是如果遇到两个比较麻烦的较大的数，比如：9193和3567，我们怎么办呢？

我们的祖先很久之前就帮我们搞定了，那个时候信息不畅，东西方人都各自用了几乎相同的方法，分别记载于欧几里得的《几何原本》（第VII卷，命题yⅠ和Ⅱ）和《九章算术》“更相减损术”中。

《几何原本》记载：

设有不相等的二数，若依次从大数中不断地减去小数，若余数总是量不尽它前面的一个数，直到最后的余数为一个单位，则该二数互素。

《九章算术》“更相减损术”：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

那么我们用最开始的例子做个计算。

9193和3567，先用9193÷3567，商2余2059，再用3567÷2059，商1余1508，2059÷1508，商1余551,1508÷551，商2余406，551÷406，商1余145，406÷145，商2余116，145÷116，商1余29，116÷29，商4除尽。所以最大公约数 29。

低年级的小朋友可以用91和49试一试。

这就是辗转相除法，大家是不是又新技能get√了！