Clever Geek Handbook

Greatest Common Factor - Upper Bound

I am curious about the GCD issue. I'm taking Coursera's Cursor Algorithms course and it claims to be a naive solution to the problem:

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

I am confused by this. Wouldn't the maximum possible divisor be min (a, b) instead of a + b? since the lesser of two cannot be divided into the greater of two?

+3


source to share


1 answer


Yes you are right. You can rewrite the algorithm so that the loop stops at min (a, b)

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


This implementation is faster than the first. You can still improve it by looping back:

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


source






More articles:


All Articles