Reputation: 148
I'm curious about the GCD problem. I am taking the Coursera Algorithmic toolbox course, and it states that the naive solution to the problem is:
for d from 1 to a+b:
if d|a and d|b:
best(or max) d
return best
I'm confused by this though. Wouldn't the maximum possible divisor be min(a,b) instead of a+b? since the smaller of the two couldn't possibly be divided by the larger of the two?
Upvotes: 3
Views: 370
Reputation: 484
Yes, you are right. You could rewrite the algorithm, that the loop stop by 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 one. You could still improve it by looping backward:
for d from min(a,b) to 1:
if d|a and d|b:
break
return d
Upvotes: 4