Question

如何求最大公因数

Answer 1

最大公因数的求法：

第一种方法是枚举法。所谓枚举法，就是将两个数的因数分别列举出来，再从中找到他们的公因数，最后从公因数中找到最大的公因数。例如求6、15的最大公因数。

6的因数：1、2、3、6。

15的因数：1、3、5、15。

他们的公因数是1、3。

所以他们的最大公因数是3。

第二种方法是短除法。先用这两个数公有的质因数同时去除这两个数，直到所得的商互质（即没有公因数）为止，再将所有的除数相乘（即短除号左边的数），乘积即为这两个数的最大公因数。这种方法最为简洁，最常用，对于较大数的最大公因数计算也很方便。

辗转相除法与更相减损术的区别

（1）都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。