finding GCD using for loop-CodePudding

I am trying to find the Greatest Common Divisor of 2 numbers using for loop, when I enter 2 numbers and one is divided by second without reminder it returns a correct answer, for example GCD(18,6) returns 18 but GCD(16,6) returns 0 instead of 2, can you help me understand why it does so? Here is what I have done so far:

best = 0  # remembers the biggest numbers seen (for that purpose, IDK if it does)
a = 16  # first number
b = 6  # second number

for i in range(1, a   b):
    if i % a == 0 and i % b == 0:
        best = i
        
print(best)

CodePudding user response：

Your modulo division is backwards, use a % i and b % i.

CodePudding user response：

You can also do this using the Euclidean Algorithm where the smaller of the two numbers is used to divide the greater in the first step, and the divisor of the first step becomes the dividend of the next step while the remainder of the first step becomes the divisor of the next step. The process continues till a remainder of zero is gotten. The divisor that gives a remainder of zero is the GCD(https://sites.math.rutgers.edu/~greenfie/gs2004/euclid.html).

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