求最大公约数，欧几里德在公元前300年的方法，比老师教的简单多了。是的，好像瞬间被拉回了学生时代。
对于有些人来说，学生时代可以说是一场漫长的噩梦，所以醒来之后，便忘记了梦中的一切。很久以前不记得了，让我们回忆一下吧。现在假设有两个整数，即A和B。如果A除以B，结果仍然是整数，那么我们称A为“B的倍数”，称B为“A的约数”。B和B这两个数的最大公约数是“最大公约数”。
大家对“质因数分解”这个词应该都有印象，但是至于什么是质因数分解，以及如何分解质因数，恐怕很少有人记得。但是不记得也没关系，既然忘记了那就忘记吧，因为通过质因数分解求最大公约数太麻烦，效率也太低了。
要求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。
边长为14的正方形放不下，只能放边长为10的正方形，剩余空间为4X10。
现在我们可以放下一个边长为4的正方形，我们放两个，这样就剩下一个4X2的区域，在这个区域放两个边长为2的正方形，刚好可以填满.现在我们知道能恰好填满这个矩形的最大正方形是边长为2的正方形，所以2是110和24的最大公约数，这个结果和欧几里德滚分法得到的结果是一样的是完全一样的。
既然有这么简单、直观、高效的方法，为什么老师还要让我们通过素因数分解来求最大公约数呢？其实原因很简单。我们在学校学到的很多知识，并不是为了解决问题，而是为了锻炼我们的思维。如果我们尝试用在学校学到的知识来解决实际问题，你可能会发现这个世界太复杂了。
热门跟贴