logo标签列表

最大公约数 - 上界

algorithm
3

我很好奇GCD问题。我正在学习Coursera算法工具箱课程，它指出该问题的朴素解决方案是：

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

我有点糊涂了。最大公因数难道不是min(a,b)而是a+b吗？因为两个数字中较小的那个不可能被较大的数字整除，对吧？
1个回答
4

是的，你说得对。你可以重写算法，让循环在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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接