最大公約數 - 上限

Question

我很好奇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？因爲兩者中的較小者不可能被兩者中的較大者所分割？

Answer 1

是的，你是對的。你可以重寫算法，該循環停止由分（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