培训机构|求最大公约数，公元前300年欧几里得的方法，远比老师教的简单
文章图片
文章图片
“求最大公约数” ， 听到这几个字 ， 是不是觉得脑袋瓜子“嗡嗡”的 ， 好像一瞬之间就被拽回了学生时代 。
对于一些人而言 ， 学生时代可以算得上是一场绵长的噩梦 ， 所以在醒来之后 ， 便把梦中的一切都抛之脑后了 ， 至于“最大公约数”是什么 ， 也早已不记得了 ， 那就让我们来回忆一下 。 现在假设有两个整数 ， 分别是A和B ， 如果A除以B之后得到的仍然是一个整数 ， 那么我们就称A为“B的倍数” ， 称B为“A的约数” ， 而A和B这两个数字的最大公共约数就是“最大公约数” 。
那么如何求得两个数字的最大公约数呢？已经记不得求解最大公约数的知识是小学学习的 ， 还是初中教授的了 ， 但求解最大公约数的方法 ， 你一定记得 ， 即便是不记得了 ， 只要一听到就会觉得似曾相识 ， 那就是“分解质因数” 。
对于“分解质因数”这个词 ， 所有人应该都有所印象 ， 但至于什么是分解质因数 ， 如何分解质因数 ， 恐怕就没有几个人记得了 。 不过不记得也不要紧 ， 既然忘了 ， 就让它忘却吧 ， 因为通过分解质因数的方法求得最大公约数实在是过于繁琐了 ， 而且效率不高 。
现在我们要来说一种非常简单且效率极高的方法 ， 不过这并不是什么新方法 ， 而是早在公元前300年就已经出现了 ， 著名的古希腊数学家欧几里得将这种方法记载在了《几何原本》之中 ， 而现在我们就将这种方法称之为辗转相除法 ， 如果我们在小学的时候就知道了这种方法 ， 那么一定能够成为班级里的“最大公约数之王” 。 现在我们就举一个实例来介绍这种简单的方法 ， 随便选两个数字 ， 110和24 。
要求110和24的最大公约数 ， 用不着去分解质因数 ， 只需要通过几步简单的除法就可以了 。
首先我们用110除以24 ， 所得到的商是4 ， 而余数是14 。 接下来我们用刚才的除数24除以余数14 ， 所得到的商是1 ， 余数是10 。 第三步用上一步的除数14除以余数10 ， 得到商是1 ， 余数是4 。 第四步用第三步的除数10除以余数4 ， 得到商是2 ， 余数是2 。 最后一步 ， 还是用上一步的除数4除以余数2 ， 得到商是2 ， 余数为0 。 余数为0就不可以再继续计算了 ， 所以最终的商2就是110和24的最大公约数 。
就是如此简单 ， 只需要学会加减乘除就可以高效率地计算最大公约数 ， 而用不着去搞什么分解质因数 。 欧几里得的方法固然简单 ， 但现实中总有些人对于数字不太感冒 ， 那也没有关系 ， 靠画图同样可以求解最大公约数 。
还是以110和24两个数字为例 ， 要通过图解法来求最大公约数 ， 首先我们就要画出一个长方形 ， 这个长方形的长为110 ， 而宽为24 。
现在我们要做的就是用大量一模一样的正方形将这个长方形填满 ， 而能够恰好将这个长方形填满的最大的正方形就是这两个数字的最大公约数 。 现在问题来了 ， 如何能够找到最大的且刚好可以将这个长方形填满的正方形呢？首先我们先在这个长方形的一边放入一个边长为24的正方形 ， 而剩余的空间为长86、宽24的长方形 。 之后再放入一个边长24的正方形 ， 剩余的空间为长62、宽24 。 继续放入边长24的正方形 ， 剩余空间为长38、宽24 。 最后再放入一个边长24的正方形 ， 剩余空间为14x24 。
现在已经放不下边长为24的正方形了 ， 所以我们放入一个边长为14的正方形 ， 剩余空间为14X10 。
推荐阅读
- 培训机构|考研复试这样准备，容易得到导师青睐
- 公司|成人学历培训机构虎硕教育停止营业：运营压力大不堪重负
- 培训机构|“双减“后首个寒假：对恶意涨价的非学科类培训班说不！
- 技术|紧扣地方需求 “炼”出真金人才
- 大学|大学哪些专业对身高要求？这6类差1cm也报不上，家长和学生要清楚
- 大学生|名牌大学生到福耀求职，曹德旺把简历丢进垃圾桶，竟安排他去拉板车
- 考研|这6个考研“冷门”专业，只求“上岸”的考生，可以试一试！
- 高考|这是高一学生最需要读的书，放假前老师反复要求，你读了没有？
- 培训机构|公务员觉得太累想辞职，最好考虑清楚！认清自己的实力
- 清华大学|刘学州因学校不能留宿求助生母，结果被拉黑，与孙卓形成鲜明对比