Question

用短除法求42,105,56的最大公因数

Answer 1

短除法的大概过程就是如此，3和754互质，因此短除停止。

gcd(a,b)表示a，b的最大公因数。

其实呢，如果题目里没说要用短除法，还有一个更快的算法可以求出两数的最大公因数，就是“欧几里得算法”，又叫“辗转相除法”，可以参考：

http://baike.baidu.com/view/255668.htm

祝学习进步

追问

是42、105、56的最大公因数

追答

no！
没看到逗号……
格式同上，结果：
gcd（42，105，56）=7

追问

要用短除法

追答

格式一样啊？
就是把三个数写在一个L形框里，左边写这三个数的一个公因数，下面写相除的结果。直到新得到的三个数互质。

而在这个题中，只要列一次就能找到最大公因数了。因为7本身也是质数。