辗转相除法

欧几里得算法是数论数学分支的一种算法。 它可以用来计算两个自然数的最 大公约数。 两个数的最 大公约数也可以从它们的质因数分解中找到。 但是，如果两个数的质因数分析都不知道，那么欧氏算法是计算最 大公约数的最快方法。

欧几里得算法不仅适用于自然数。 相反，它可以用来计算任何欧几里德环的两个元素的最 大公约数。 这些包括，例如，身体上的多项式。

欧几里得通过寻找两条线的长度的共同“度量”来计算最 大公约数。 为此，他反复从较大的两个长度中减去较小的那个。 在这样做时，他利用了这样一个事实，即如果从较大的数字中减去较小的数字，则两个数字（或长度）的最 大公约数不会改变。

如果 a  和 b之间的差异非常大，则可能需要许多减法步骤。

现在通常使用下面描述的除法算法，其中步骤 2 和 3 被替换而不是取 m  和 n 的差，因为 r  在 m 时取余数除以 n 。 这种变体的另一个优点是它可以转移到经典算法不起作用的任何欧几里得环（例如域上的多项式环）。

如今，经典算法中重复减去一个值的每一步都被一次除法和余数所取代。现代欧几里得算法现在在每一步中执行这种除法和余数。 它以两个数字 a  和 b = r 0开头，它们的最 大公约数有待确定。

a = q 1 ⋅ r 0 + r 1

在每个进一步的步骤中，使用除数和前一步的余数执行新的余数除法，并继续进行直到可以进行除法，即余数为零。

下面的 C++ 编程语言程序显示了递归变体和迭代变体的实现。 这两个变体分别在具有参数 a 和 b 的函数中实现。 在执行程序时，使用了主函数 main，它允许通过控制台输入两个数字，然后在那里输出两个变体的结果。