banchan86
5/20/2017 - 4:04 PM

Euclidean algorithm for computing greatest common divisor (GCD)

Euclidean algorithm for computing greatest common divisor (GCD)

# Uses python3

def Euclid_GCD(a, b):
    if b == 0:
        return a
    a_prime = a%b
    return Euclid_GCD(b,a_prime)

input = input()
a, b = map(int, input.split())
print(Euclid_GCD(a, b))