Question

如何快速求两数的最大公因数？

Answer 1

短除法是求最大公因数的一种方法，也可用来求最小公倍数。

15和16的最大公因数为1。做法如下：

从1开始，因为15和16互质，没有其它的数字可以除了。

扩展资料：

求两个数字的最大公因数还可以用到欧几里得算法。

1、欧几里得算法又叫辗转相除法，欧几里德算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里德算法。

2、计算公式gcd(a,b) = gcd(b,a mod b)。

参考资料：百度百科-欧几里得算法