直观了解GCD算法

Question

什么是理解该算法如何找到GCD的直观方法？

Answer 1

维基百科有名字Euclidean algorithm下它的好文章。特别是，从文章这一形象可能会回答你的文字问题：直观的方式了解该算法如何找到最大公约数：欧几里得算法的

基于减法的动画。最初的矩形的尺寸为a = 1071和b = 462.尺寸为462×462的正方形放置在其中，留下462×147的矩形。该矩形与147×147平方平铺，直到剩下一个21×147矩形，而矩形依次与21×21平方平铺，不留下未覆盖区域。最小平方大小，图21，是1071的GCD和462

Answer 2

总之，如果两者a和b是可分割由D那么它必须是a-b除数和不能大于a-b更大。其中的逻辑是用加法规则，对于a=b的GCD是a的应用这个递归：

GCD(a, b) = a == b ? a : GCD(min(a, b), abs(a-b)) 

Answer 3

最大公约数算法的最初发明者是欧几里德，谁在他的书中描述IT元素约在基督诞生之前的300年。这里是他的几何解释，包括他的图：

设AB和CD是两个给定数字不互质。

需要找到AB和CD的最常用测量。

如果现在CD测量AB，因为它也测量自身，那么CD是CD和AB的常用量度。很明显，它也是最大的，没有比CD措施CD更多的数字。

但是，如果CD不测量AB，那么当AB和CD中的较少数连续从较大的数中减去时，留下一些数来测量它之前的数。

对于一个单位没有离开，否则AB和CD将是相对的素数，这是违背假设的。

因此，剩下一些数字用于衡量前面的数字。

现在让CD，测量BE，让EA比自己小，让EA，测量DF，让FC小于自身，并让CF测量AE。此后，CF测量AE，AE测量DF，因此CF也测量DF。但它自我衡量，因此它也衡量整个CD。

但CD措施BE，所以CF也措施BE。它也衡量EA，因此衡量整个BA。

但它也测量CD，因此CF测量AB和CD。因此CF是AB和CD的常用量度。

我接下来说它也是最大的。

如果CF不是AB和CD的最常用量度，那么一些大于CF的数字G就会测量AB和CD的数量。

现在，由于G测量CD，CD测量BE，因此G也测量BE。但它也测量整个BA，因此它测量剩余的AE。

但AE测量DF，因此G也测量DF。它测量整个DC，因此它也测量剩余的CF，即越大的措施越少，这是不可能的。

因此，没有大于CF的数字测量数字AB和CD。因此CF是AB和CD最常见的衡量标准。

观察到Euclid使用单词“度量”来表示某个更小长度的倍数与更大的长度相同;也就是说，他的概念“措施”与我们在7分28中的概念“分歧”是一样的。