CODEWITHSUNDEEP
pythonpython-2.7python-3.xmath
B Hok
B Hok

Reputation: 155

Finding Greatest Common Divisor through iterative solution (python 3)

I am trying to find the great common divisor by using a function and solving it iteratively. Though, for some reason, I am not sure why I am not getting the right output.

The greatest common divisor between 30 & 15 should be 15, however, my output is always giving me the wrong number. I have a strong feeling that my "if" statement is strongly incorrect. Please help!

def square(a,b):
    '''
    x: int or float.
    '''
    c = a + b

    while c > 0:
        c -= 1
        if a % c == 0 and b % c == 0:
            return c
        else: 
            return 1

obj = square(30,15) 
print (obj)

Upvotes: 0

Views: 6692

Answers (2)

Uriel
Uriel

Reputation: 16184

You should return a value only if you finished iterating all numbers and found none of them a divisor to both numbers:

def square(a, b):
    c = a + b

    while c > 0:
        if a % c == 0 and b % c == 0:
            return c
        c -= 1
    return 1

However, the last return will be unneeded in this case, as c would go from a + b to 1, and mod 1 will always bring a common divisor, so the loop will always terminate with 1, for the worst case.

Also, a number greater than a and b can not be a common divisor of them. (x mod y for y > x yields x), and gcd is the formal name for the task, so I would go with 

def gcd(a, b):
    for c in range(min(a, b), 0, -1):
        if a % c == b % c == 0:
            return c

for iterational solution.

Upvotes: 3

Chris Mueller
Chris Mueller

Reputation: 6680

You might be interested to know that there is a common recursive solution to the GCD problem based on the Euclidian algorighm.

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

print(gcd(30, 15))
# 15

Upvotes: 0

Related Questions