algorithm - 最大公约数 - 上限

Question

我很好奇 GCD 问题。我正在参加 Coursera 算法工具箱类(class)，它指出问题的天真解决方案是:

for d from 1 to a+b:
    if d|a and d|b:
        best(or max) d
return best

虽然我对此感到困惑。最大可能的除数不是 min(a,b) 而不是 a+b 吗？因为两者中较小的不可能除以两者中较大的？

Answer 1

是的，你是对的。您可以重写算法，使循环停止于 min(a,b)

for d from 1 to min(a,b):
    if d|a and d|b:
        best(or max) d
return best

这个实现比第一个更快。您仍然可以通过向后循环来改进它:

for d from min(a,b) to 1:
    if d|a and d|b:
       break
return d