最大公约数算法流程图最大公约数怎么求算法 _知识经验

“求最大公约数”，听到这几个字，是不是觉得脑袋瓜子“嗡嗡”的，好像一瞬之间就被拽回了学生时代。
【最大公约数算法流程图最大公约数怎么求算法】对于一些人而言，学生时代可以算得上是一场绵长的噩梦，所以在醒来之后，便把梦中的一切都抛之脑后了，至于“最大公约数”是什么，也早已不记得了，那就让我们来回忆一下。
现在假设有两个整数，分别是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 。