why isn't my python loop iterating? it works if gcd is = a or b but it doesn't iterate

Riham Jamal 0
Viewed 37

a, b: positive integers returns: a positive integer, the greatest common divisor of a & b.

def gcdIter(a, b):
 
    if a < b:
        gcd = a
    else: 
        gcd = b
    while gcd > 0:
        if a % gcd != 0 and  b % gcd != 0:
            gcd -= 1
        else:
            return gcd
print(gcdIter(9, 12))
while-loop python
2 Answers

Your code is attempting to find GCDs in a brute force fashion by starting with the smaller of the two numbers and then working down to the GCD. This isn't efficient, but should work. Your code decrements gcd if it isn't a divisor of both. You need to decrement it if it isn't a divisor of either. To do this, swap and for or:

def gcdIter(a, b):
 
    if a < b:
        gcd = a
    else: 
        gcd = b
    while gcd > 0:
        if a % gcd != 0 or b % gcd != 0:
            gcd -= 1
        else:
            return gcd
print(gcdIter(9, 12))

Which prints 3.

Having said all that, a dramatically more efficient approach is to study and implement the Euclidean Algorithm.

John Coleman0 
def gcdIter(a, b):
    if b>a:
        a,b=b,a
    while b:
        a,b = b,a%b
    return a

print(gcdIter(20,5))
islam abdelmoumen0
Related