Question

求两个数的最大公约数

Answer 1

求两个数的最大公约数有下列几种方法：

欧几里得算法：

例如求1997和615的最大公因数的步骤：

1997/615=3（余152）。

615/152=4（余7）。

152/7=21（余5）。

7/5=1（余2）。

5/2=2(余1)。

2/1=2(余0)。

至此1997和615的最大公约数为1，以除数和余数反复做运算，最后余数为0，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1，这是欧几里得算法。

枚举法

给出 m 和 n，首先求出 m 和 n 的最小值赋值给临时变量 t，然后对 t 依次递减，如果 m 除以 t 的余数为 0，并且 n 除以 t 的余数为 0，此时 t 就是 m 和 n 的最大公约数，这是枚举法。

公共积子因

算法简介：通过计算两个数字的公共积子因。

算法描述：计算 gcd(m, n)

第一步:找出 m 的全部质因数。

第二步:找出 n 的全部质因数。

第三步:从第一步和第二步求得的质因数分解式中找出所有的公因数(如果p是一个公因数,而且在m和n的质因数分解式分别出现过pm和pn 次,那么应该将p重复min{pm, pn}次)。

第四步:将第三步中找到的质因数相乘,其结果作为给定数字的最大公约数。