求最大公约数的几种方法

最近在辅导我儿子学习 Python 编程，很多算法的步骤中都会涉及到求最大公约数的问题，因此我将不同的算法实现记录在这里。

枚举法

枚举法是最容易理解的方式，利用公约数的定义，从两个数中较小的一个数开始，不断比较该数与两个数相除的余数是否都为零。代码实现如下:

def enumFromMin(num1, num2):
    if num1 < num2:
        num1, num2 = num2, num1
    for i in range(num2 - 1, 0, -1):
        if num1 % i == 0 and num2 % i == 0:
            return i

枚举法虽然理解起来简单，但时间复杂度比较高，比如我们求 27和21 的最大公约数，用枚举法需要18步（循环18次），而且每次需要进行两个数的取余操作，如果两个数都比较大的时候，会非常耗时，因此在实际工作中要尽量避免使用。

辗转相除取余法

算法描述如下:

已知两个整数 num1 和 num2, 求最大公约数:

num1 除以 num2, 取余数为 ok
若 ok 等于零，则 ok 即为 num1 和 num2 的最大公约数
若 ok 不等于零，则 num1 = num2, num2 = ok, 在回到第一步开始

对应的代码如下:

def loopDivision(num1, num2):
    ok = num1 % num2
    while ok != 0:
        num1, num2 = num2, ok
        ok = num1 % num2
    return num2

同样求27和21 的最大公约数，只需要3步即可完成，只需要三次取余计算。

循环相减法

算法描述如下:

已知两个整数 num1 和 num2, 求最大公约数:

如果 num1 > num2, 则 num1 = num1 - num2
如果 num1 < num2, 则 num2 = num2 = num1
如果 num1 等于 num2, 则找到了最大公约数（num1 或 num2 皆可，因为二者相等)
如果 num1 不等于 num2，则回到第一步执行

代码如下:

def loopSubstraction(num1, num2):
    while num1 != num2:
        if num1 > num2:
            num1 = num1 - num2
        else:
            num2 = num2 - num1
    return num1

同样求27和21 的最大公约数，只需要5步即可完成。