求最大公约数欧几里得算法(求最大公约数的公式是啥?)

求最大公约数，公元前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。

边长为14的正方形也放不下了，于是我们只能放入一个边长为10的正方形，剩余空间为4X10。

现在能够放下边长为4的正方形了，我们放入两个，这样就剩下了一个4X2的区域，在这个区域之中放入两个边长为2的正方形，刚好可以将其填满。现在我们就知道了，能够恰好将这个长方形填满的最大的正方形就是边长为2的正方形，所以2就是110和24的最大公约数，这个结果与欧几里得的辗转相除法所得的结果是完全一样的。

既然有如此简单直观、效率又高的方法，为什么老师还要让我们通过分解质因数的方法来求最大公约数呢？其实原因很简单，我们在上学的时候所学的很多知识并不是用于解决问题的，而是用来锻炼思维的，如果我们企图用学校学的知识来解决实际问题，你可能会发现这个世界太过复杂了。

温馨提示：通过以上关于求最大公约数，公元前300年欧几里得的方法，远比老师教的简单内容介绍后，相信大家有新的了解，更希望可以对你有所帮助。