简介
两个或多个正整数数的公约数是，对于这些数，存在一个正整数，可以整除它们。公约数可能有若干个，而其中最大的就是最大公约数。
也就是：
A: card(A) ≥ 2, (∀ a ∈ A, a ∈ N*) ;
B = {n ∈ N* | ∀ x ∈ A, x mod n = 0};
k = max{B};
k即为A中各数的最大公约数。
从人类的做法推导
我们计算最大公约数的时候，通常用短除法来计算。具体的方法是：同时让这些数除以一个比较小的公约数，得到的结果再这样操作，直到找不到大于等于2的公约数；将除数相乘即得到最大公约数。比如：
短除法计算最大公约数
通过经验，人是可以快速找到一些较小的公约数，写在除数上的。但是，计算机却无法这么做。但是计算机可以从1开始，判断某个整数是否能整除所有给定的数。如果能，即为公约数，记下来；否则，除数加1，再试。
但是，算法是有限的，到什么时候停止呢？根据常理，一组数的最大公约数一定不大于这组数的最小的数。因此，如果算到这组数的最小值的话，就不用再算下去了。
由此可以推导出流程图如下：
计算最大公约数流程图(1)
鉴于1能够整除所有正整数，我们可以让循环从2开始。这样，流程图如下：
计算最大公约数流程图(2)
如果我们把“∀ a ∈ A, a mod i = 0?”的判断展开，则如下：
计算最大公约数流程图(3)
已经非常复杂了。
实际应用中，我们更多的是计算两个数之间的最大公约数。这样，流程图可以简化如下：
计算两个数的最大公约数流程图
不过这个方法在计算的时候，如果是小的数字还可以，遇到大数的时候，计算时间就非常长。
这时候还可以使用更加简便的算法。
辗转相除法
辗转相除法又称欧几里得算法，首次出现于《几何原本》中，被人们认为是史上第一个算法。它可以用于求两数的最大公约数。
首先，用两数中较大数除以较小数，求得数；再用较小数和余数按上述操作进行相除；直到余数为0。此时的除数即为最大公约数。
流程图表示如下：
辗转相除法(1)
考虑到许多编程语言使用的是DO-WHILE型的直到型循环结构，还有一些语言没有直到型循环结构，流程图改写为如下：
辗转相除法(2)
其中当型的流程图在循环结构前有一个定义变量r的操作。这里的r的赋值只要不等于0就可以了。
此外，还有递归型的流程图：
辗转相除法(递归)
更相减损术
更相减损术是《九章算术》中给出的求两个数的最大公约数的方法：
可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
算法描述为：
第一步：任意给两个正整数；判断它们是否都是偶数，如果是，用2约简，并记下次数；否则，进行下一步；
第二步：以较大的数减去较小的数，把差与较小的数相比，并用大数减小数。继续此操作，使所得数相等为止。记下这个数。
第三步：如果第一步有约简，第二步所得的数乘上2乘约简次数就是最大公约数。否则，第二步所得的数就是最大公约数。
（人教版的教科书上对这个的解释有问题……粗体字表示增加的内容）
流程图如下：
更相减损术(1)
标准化后如下：
更相减损术(2)
看起来非常麻烦。
不过，还有一个简单的算法：
更相减损术(3)
实际上这和辗转相除法很相似了。在维基百科上，它们是在一个词条内的，而且上面的算法被称为欧几里得算法的减法形式。
三者的比较
在现代，算法之间的比较主要体现在效率上。在下面，我将使用IPython的工具来测试它们的运行速度（使用语言为Python，在安装Windows 10 专业版和Python 3.6的华硕N551ZU上进行，结果仅供参考）。
各种算法的执行时间测试
从这里就能看出来，虽然现在电脑硬件水平的发展相当成熟，但是各个算法之间的运行速度还是有比较明显的差别的。
之前的那个直接求最大公约数的方法，运算速度相对于其他的算法都比较慢，尤其是在两个数都非常大的情况下。相比之下，其他算法的运算速度和它的运算速度相差悬殊。
另外，更相减损术在两数相差悬殊的时候，运算速度也会减慢。
从这里我们可以看出优化算法的意义——可以显著减少运行时间，提高效率，节能。这个测试还是在比较好的机器上进行的，如果是在简单的单片机上，差别就更加明显了。
参考资料
如果大家想了解关于这两个算法的更多内容，也可以看看。
- 辗转相除法 - 维基百科，自由的百科全书
https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95 - 普通高中课程标准实验教科书（必修） 数学（A版） 必修3. 人民教育出版社
- 辗转相除法、更相减损法、Stein算法 - CSDN博客
http://blog.csdn.net/Holmofy/article/details/76401074
网友评论