gcd.py asks you to implement a function that returns the greatest common divisor for number a, b. A naive implementation is given to you but it runs very slow. Your goal is to implement Euclids algorithm for computing GCD. You can find how the algorithm works in Wikipedia (https://en.wikipedia.org/wiki/Euclidean algorithm).

# python3 def gcd_naive(a, b): assert 1 <= a <= 2 * 10 ** 9 and 1 <= b <= 2 * 10 ** 9 for divisor in range(min(a, b), 0, -1): if a % divisor == 0 and b % divisor == 0: return divisor assert False def gcd(a, b): assert 0 <= a <= 2 * 10 ** 9 and 0 <= b <= 2 * 10 ** 9 # START CODE HERE # END CODE HERE if __name__ == '__main__': input_a, input_b = map(int, input().split()) print(gcd(input_a, input_b))