前言:
现时大家对“如何求最大公约数算法”大体比较关心,看官们都需要知道一些“如何求最大公约数算法”的相关文章。那么小编也在网摘上收集了一些关于“如何求最大公约数算法””的相关内容,希望咱们能喜欢,看官们快快来了解一下吧!这有什么不会的~
比如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的最大公约数
觉得我们的知识板块棒棒哒?赶紧转发到朋友圈让给更多的人一起参与进来吧!
标签: #如何求最大公约数算法