CODEWITHSUNDEEP
algorithm
Rampant
Rampant

Reputation: 148

Greatest Common Divisor - Upper bound

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

Answers (1)

Ayoub Falah
Ayoub Falah

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

Related Questions