龙空技术网

你会算最大公约数吗?

数学学习故事 386

前言:

现时大家对“如何求最大公约数算法”大体比较关心,看官们都需要知道一些“如何求最大公约数算法”的相关文章。那么小编也在网摘上收集了一些关于“如何求最大公约数算法””的相关内容,希望咱们能喜欢,看官们快快来了解一下吧!

这有什么不会的~

比如18和30,18的约数有1、2、3、6、9、18;30的约数有1、2、3、5、6、10、15、30。18和30的最大公约数就是6。

哈哈,你就会这么LOW的方法吗?

求解最大公约数的问题,当然有更加高级一点方法了。我主要是怕你不理解,才一一列举,慢慢找出来的。你看18和30的最大公约数,我还可以用短除法来快速找出来:

先用两个数共有的质因数连续去除,一直除到所得的商是互为质数,最后把所有除数乘起来就是最大公约数,这就是短除法,因此得出18和30的最大公约数:2×3=6。

怎样? 难不住我吧!

就会这些解决简单数字的的计算方法吗?

难道你还有方法?

当然了,短除法帮助我们求解最大公约数,偶尔通过观察也能算出公约数,但是如果公约数比较大而且根据我们的观察又不能得到公约数,这个时候怎么办呢?就用到另外一种简单的方法了!

说来听听!

哈哈!坐好认真听好了!

比如,我们计算18和30的最大公约数。是这么计算的:

先用两个数中的大数除以小数 (25÷10=2······5 )

再用两个数中的小数继续除以余数 (10÷5=2······0)

如果还有余数,就用上次的余数除以新的余数……,一直除到最后没有余数为止。上面就是除了2次就没有余数了。最大公约数就是最后一次除法算式中的除数6。

这种不停的除,一直除到最后的余数是0的方法叫辗转相除法, 是由古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里德算法。

没看懂?不急,再看一道稍微难一点的!求出 222 和 407 的最大公约数。

第一步:407÷222余数是185

第二步:222÷185余数是37

第三步:185÷37余数是0

所以222和407的最大公约数就是37。

古希腊人固然聪明,可我们中华炎黄子孙也不差。

更相减损术, 出自于中国古代的《九章算术》,也是一种求最大公约数的算法。和辗转相除法非常相似,一个是不停的除,一个是不停的相减。

比如 18和30的最大公约数

第一步:30-18=12

第二步:18-12=6

第三步:12-6=6

第四步:6-6=0

所以最大公约数就是6。

明白了吗?

来练几道看看吧!

求出39和24的最大公约数

求出391和299的最大公约数

求出4081和20723的最大公约数

觉得我们的知识板块棒棒哒?赶紧转发到朋友圈让给更多的人一起参与进来吧!

标签: #如何求最大公约数算法