最大公約数 - 上段

Question

私はGCDの問題について興味があります。私はコーセラアルゴリズムツールボックスのコースを取っていて、それが問題の素朴な解決策があると述べている：

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

私はこのかかわらで困惑しています。 + bの代わりにmin（a、b）を最大可能除数ではないでしょうか？ 2つのうちの小さい方が2つのうち大きい方で割れない可能性があるからです。

Answer 1

はい、あなたは正しいです。

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