# Euclid's greatest common divisor algorithm.

# Euclid's algorithm can be described as follows.

# given two numbers:
# 1. divide the larger number by the smaller number and find the remainder.
# 2. replace the larger number by the remainder found above.
# 3. repeat 1 and 2 until one of the two numbers is zero
# 4. the gcd is the remaining (non-zero) number.


a,b = input("Enter two numbers:")

while (a!=0 and b!=0):   # equivalent to not(a==0 or b==0)
    if a>b: a= a%b
    else: b = b%a
#while
gcd = a+b   # either a or b will be zero

print "the gcd is", gcd