Go to Greatest Common Divisor, you will see two files there. gcd.py asks you to implement a function that

returns the greatest common divisor for number a, b. And the file is the unit test file.

The greatest common divisor GCD(a,b) of two positive integers a and b is the largest integer d that divides both a and b. The solution of the Greatest Common Divisor Problem was first described (but not discovered!) by the Greek mathematician Euclid twenty three centuries ago. But the name of a mathematician who discovered this algorithm, a century before Euclid described it, remains unknown. Centuries later, Euclids algorithm was re-discovered by Indian and Chinese astronomers. Now, efficient algorithm for computing the greatest common divisor is an important ingredient of modern cryptographic algorithms.

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

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