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

Question

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))

Because `9%9` is `0` so the control goes to `else` condition which returns `9` — ThePyGuy, Sep 17 '22 at 12:08
The logic seems convoluted. Why not use the Euclidean algorithm? — John Coleman, Sep 17 '22 at 12:15
@JohnColeman i havent gotten to that part of the python course yet — Riham, Sep 17 '22 at 12:19
Of course it skips *to* the `else:` part because one of the conditions in the `if` part will always fail. — quamrana, Sep 17 '22 at 12:27
This is a simple logic problem. Please carefully think about the line `if a % gcd != 0 and b % gcd != 0:`. Consider what happens if `a` is equal to 9, `b` is equal to 12, and `gcd` is equal to `9`. — Karl Knechtel, Sep 17 '22 at 12:31
I was reading it skips the else part. My fault. Yes it skips to the else and then returns immediately — Rabinzel, Sep 17 '22 at 12:31
@quamrana do you have close votes left today? Please use /questions/2168603/de-morgans-rules-explained. There's also /questions/26337003/why-does-non-equality-check-of-one-variable-against-many-values-always-return-tr but it's harder to apply in this case (because "variable" and "value" are the wrong way around, though it doesn't matter). — Karl Knechtel, Sep 17 '22 at 12:32

score 2 · Accepted Answer · answered Sep 17 '22 at 12:31

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.

score 1 · Answer 2 · answered Sep 17 '22 at 12:16

1

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

print(gcdIter(20,5))

answered Sep 17 '22 at 12:16

islam abdelmoumen

662
1
3
9

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

2 Answers2