Problem:
Greatest Common Divisor Write a program which finds the greatest common divisor of two natural numbers a and b  Input  a and b are given in a line sparated by a single space. Output Output the greatest common divisor of a and b . Constrants 1 ≤ a , b ≤ 10 9  Hint You can use the following observation: For integers x and y , if x ≥ y , then gcd( x , y ) = gcd( y , x % y ) Sample Input 1 54 20 Sample Output 1 2 Sample Input 2 147 105 Sample Output 2 21

Solution (Python):
def calc_gcd(x, y):
    """
    math.gcd()????????¨??§????????????python3.5??\??????AOJ???python?????????????????????3.4????????§?????¨??§?????????
    """
    if y == 0:
        return x
    else:
        return calc_gcd(y, x % y)


if __name__ == '__main__':
    data = [int(x) for x in input().split(' ')]
    result = calc_gcd(data[0], data[1])
    print('{0}'.format(result))

Solution (Python):
def greatest_common_divisor(a, b):
  if a == 0 or b == 0:
    return max(a, b)

  return greatest_common_divisor(max(a, b) - min(a, b), min(a, b))

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

Solution (Python):



"""
input:
147 105

output:
21
"""

import sys


def gcd(x, y):
    if x < y:
        x, y = y, x

    while y > 0:
        r = x % y
        x = y
        y = r

    return x


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1, n2 = map(int, _input[0].split())
    print(gcd(n1, n2))

Solution (Python):



"""
input:
147 105

output:
21
"""

import sys


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1, n2 = map(int, _input[0].split())
    print(gcd(n1, n2))

Solution (Python):
A,B=list(map(int,input().split()))

def gcd(A, B):
	if B==0: return(A)
	else: return(gcd(B, A%B))

print(gcd(A,B))

Solution (Python):


def gcd(num_a, num_b):
    if num_b == 0:
        return num_a
    elif num_a == 0:
        return num_b

    if num_a < num_b:
        return gcd(num_a, num_b % num_a)
    else:
        return gcd(num_b, num_a % num_b)

num_a, num_b = [int(x) for i, x in enumerate(input().split()) if i < 2]
print(gcd(num_a, num_b))

Solution (Python):
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

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

Solution (Python):
data = list(map(int, input().split()))
a,b = max(data), min(data)
r = a % b

while r != 0:
    a = b
    b = r
    r = a % b

print(b)

Solution (Python):
def gcd(x, y):
	if x < y:
		tmp = y
		y = x
		x = tmp
	
	if x % y == 0:
		return y
	else:
		return gcd(y, x % y)



l = raw_input()

x, y = [int(e) for e in l.split()]
 
if x < 1 and x > 10000000000:
	exit()

if y < 1 and y > 10000000000:
	exit()

print gcd(x, y)

Solution (Python):



def gcd(x, y):
    
    if x < y:
        x, y = y, x

    while y > 0:
        r = x % y
        x = y
        y = r

    print(x)


def to_xy(v):
    return [int(c) for c in v.split()]


if __name__ == '__main__':
    x, y = to_xy(input())
    gcd(x, y)

Solution (Python):
x, y = map(int, input().split())
while y>0: x, y = y, x%y
print(x)

Solution (Python):
a,b=map(int,input().split())
while b: a,b=b,a%b
print(a)

Solution (Python):

a,b = map(int,input().split())
while True:
    r=a%b
    if r==0:
        break
    else:
        a=b
        b=r
print(b)

Solution (Python):

def gcd(x, y):
    if x >= y:
        x = x % y
        if x == 0:
            return y
        return gcd(x, y)
    else:
        y = y % x
        if y == 0:
            return x
        return gcd(x, y)

x, y = map(int, input().split())
print(gcd(x, y))

Solution (Python):

def gcd(a, b):
    while a > 0:
        if a < b: a, b = b, a
        a = a % b
    return b

x, y = map(int, input().split())
print(gcd(x, y))

Solution (Python):

def gcd(n,m):
    if n < m:
        tmp = m
        m = n
        n = tmp
    while m > 0:
        r = n % m
        n = m
        m = r
    return n
    
x, y = map(int,input().split())
print(gcd(x,y))

Solution (Python):
def gcd(x, y):
    x, y = max(x, y), min(x, y)
    while y != 0:
        x, y = y, x % y
    return x

X, Y = (int(s) for s in input().split())
print(gcd(X, Y))

Solution (Python):
def gcd(x, y):
    while y != 0:
        x,y = y, x % y
    return x

A = list(map(int,input().split()))
print(gcd(A[0], A[1]))

Solution (Python):
x, y = map(int, input().split())
if x < y:
    x,y = y,x
while y:
    x,y = y, x%y
print(x)

Solution (Python):
a,b=map(int,input().split())
while b:
 a,b=b,a%b
print(a)

Solution (Python):
x, y = [int(i) for i in input().split()]

if x < y:
    a = x
    x = y
    y = a

def kouyakusu(x,y):
    yakusu = x % y
    if yakusu == 0:
        print(y)
        return y
    else:
        kouyakusu(y,yakusu)

max_kouyakusu = kouyakusu(x,y)

Solution (Python):
def gcd (x , y):
  sur = x % y
  while sur != 0:
    x = y
    y = sur
    sur = x % y
  return y

a,b = map(int,raw_input().split())
if a < b :
  temp = a
  a = b
  b = temp
print gcd(a,b)

Solution (Python):
x, y = map(int,input().split())
while True:
  if x >= y:
    x %= y
  else:
    y %= x
  if x == 0 or y == 0:
    print(x+y)
    break

Solution (Python):
x,y = map(int,input().split())
while y:
    x,y = y, x%y
print(x)

Solution (Python):
a,b = map(int,input().split())

if a<b:
    ret = a
    a = b
    b = ret


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

print(str(gcd(a,b)))

Solution (Python):
x, y = map(int, input().split())

if x < y:
		x, y = y, x

while y > 0:
	x, y = y, (x%y)

print(x)

Solution (Python):
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

x, y = map(int, input().split())
print(gcd(x, y))

Solution (Python):
def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x

x, y = map(int, input().split())
print(gcd(x, y))

Solution (Python):



def converter(a, b):
    larger = max(a, b)
    smaller = min(a, b)
    if larger == 0 or smaller == 0:
        return larger
    else:
        return converter(smaller, larger % smaller)        


def main():
    a, b = [int(x) for x in raw_input().strip().split(' ')]
    print converter(a, b) 


if __name__ == '__main__':
    main()

Solution (Python):



def converter(a, b):
    larger = max(a, b)
    smaller = min(a, b)
    if smaller == 0:
        return larger
    else:
        return converter(smaller, larger % smaller)        


def main():
    a, b = [int(x) for x in raw_input().strip().split(' ')]
    print converter(a, b) 


if __name__ == '__main__':
    main()

Solution (Python):



def converter(a, b):
    larger = max(a, b)
    smaller = min(a, b)
    if smaller == 0:
        return larger
    else:
        return converter(smaller, larger % smaller)        


def main():
    a, b = [int(x) for x in raw_input().strip().split(' ')]
    print converter(a, b) 


if __name__ == '__main__':
    main()

Solution (Python):



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


def main():
    a, b = sorted([int(x) for x in raw_input().strip().split(' ')])
    print converter(a, b) 


if __name__ == '__main__':
    main()

Solution (Python):
def converter(a, b):
    if b%a == 0:
        return a
    else:
        return converter(b % a, a)


def main():
    a, b = sorted([int(x) for x in raw_input().strip().split(' ')])
    print converter(a, b) 


if __name__ == '__main__':
    main()

Solution (Python):
def converter(a, b):
    if b%a == 0:
        return a
    else:
        return converter(b % a, a)


a, b = sorted([int(x) for x in raw_input().strip().split(' ')])
print converter(a, b)

Solution (Python):
def converter(a, b):
    if b%a == 0:
        return a
    else:
        return converter(b % a, a)


a, b = sorted([int(x) for x in raw_input().split(' ')])
print converter(a, b)

Solution (Python):
a, b = map(int, input().rstrip().split(" "))

if a > b:
    A = a
    B = b
else:
    A = b
    B = a

GCD = 1
while True:
    A, B = B, A%B
    
    if B == 0:
        break
    
print (str(A))

Solution (Python):


def mcg(a,b):
    if a==b:
        return a
    else:
        
        while a%b !=0:
            x = a%b
            a = b
            b = x
        return x

num =sorted(list(map(int,input().split(" "))))
print(mcg(num[0],num[1]))

Solution (Python):
def gdc(a,b):
    
    if min(a,b) == 0:
        return a
    else:
        return gdc(min(a,b), max(a,b)%min(a,b))
        
a = [int(s) for s in input().split(" ")]
print(gdc(a[0],a[1]))

Solution (Python):

def gcd(a, b):
    if b>a:
        b, a = a, b

    d = 1
    while True:
        d = a % b
        if d == 0:
            break
        a, b = b, d

    return b


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

Solution (Python):
import sys

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a




input = sys.stdin.readline()
input = input.split(" ")
input = [int(i) for i in input]

print(gcd(input[0], input[1]))

Solution (Python):
a, b = [int(tem) for tem in input().split()]

def mak(A, B) :
    while B != 0 :
        q, r = divmod(A, B)
        A = int((A - r) / q)
        B = r
    return A

if a > b : print(mak(a, b))
else     : print(mak(b, a))

Solution (Python):


import sys
import os
import math


a, b = list(map(int, input().split()))

if b > a:
    a, b = b, a

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

result = gcd(a, b)
print(result)

Solution (Python):
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

s=input().split()
a=int(s[0])
b=int(s[1])

y = gcd(a,b)
print(y)

Solution (Python):
def gcd(a,b):
    if a>b:
        x=a
        y=b
    else:
        x=b
        y=a

    if y==0:
        return x
    else:
        return gcd(y,x%y)

p,q=[int(i) for i in input().split(" ")]
print(gcd(p,q))

Solution (Python):
tmp=input().split()
m=int(tmp[0])
n=int(tmp[1])

while(m!=n):
    if(m>n):
        m=m-n
    else:
        n=n-m

print(m)

Solution (Python):
def gcd(x, y):
    if x % y == 0:
        return y
    else:
        return gcd(y, x % y)


x, y = list(map(int, input().split()))
print(gcd(x, y))

Solution (Python):
x, y = map(int, input().split())
a = max(x, y)
b = min(x, y)

while a%b != 0:
    temp = a
    a = b
    b = temp%b

print(b)

Solution (Python):
def gcd(a,b):
    x = max(a,b)
    y = min(a,b)

    while True:
        n = x%y
        if n == 0:
            print(y)
            break
        else:
            x = y
            y = n


a,b = map(int,input().split())
gcd(a,b)

Solution (Python):
def gcd(a,b):
    x,y = (a,b) if a>b else (b,a)
    if x % y == 0:
        return y
    else:
        return gcd(y, x % y)

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

Solution (Python):
import sys

def solve():
    a, b = map(int, input().split())
    ans = gcd(a, b)
    print(ans)

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

if __name__ == '__main__':
    solve()

Solution (Python):
def lcd(a,b): 
    if a > b:
        return lcd(a-b,b)
    elif a < b:
        return lcd(b-a,a)
    elif a == b:
        return a

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

Solution (Python):
def gdc(x, y):
    if x % y == 0:
        return y
    else:
        return gdc(y, x%y)


if __name__ == '__main__':
    x, y = [int(i) for i in input().split(" ")]
    print(gdc(x, y))

Solution (Python):
def gcd(x, y):
    '''??????????????????????????????
    x>=y?????¨??????gcd(x, y)??¨gcd(y, x%y)?????????????????¨????????¨??????'''

    if x < y:
        tmp = x
        x = y
        y = tmp

    while y > 0:
        tmp = x % y
        x = y
        y = tmp

    return x
    
def test():
    '''??? input =
    147 105
    ->
    21'''

    x, y = map(int, input().split())

    result = gcd(x, y)
    print(result)

if __name__ == '__main__':
    test()

Solution (Python):
def gcd(x, y):
    '''??????????????????????????????
    x>=y?????¨??????gcd(x, y)??¨gcd(y, x%y)?????????????????¨????????¨??????'''

    if x < y:
        x, y = y, x

    while y > 0:
        x, y = y, x % y

    return x
    
def test():
    '''??? input =
    147 105
    ->
    21'''

    x, y = map(int, input().split())

    result = gcd(x, y)
    print(result)

if __name__ == '__main__':
    test()

Solution (Python):
def gcd(x, y):
    if x < y:
        x, y = y, x

    while y > 0:
        x, y = y, x % y

    return x
    
if __name__ == '__main__':
    x, y = map(int, input().split())

    result = gcd(x, y)
    print(result)

Solution (Python):

def gcd(x,y):
    if x%y == 0:
        print(y)
    else:
        gcd(y,x%y)

x,y = [int(x) for x in input().split()]
if x>y:
    gcd(x,y)
else:
    gcd(y,x)

Solution (Python):
def gcd(x, y):
    if x > y:
        return gcd(y, x)
    if y % x == 0:
        return x
    else:
        return gcd(y % x, x)


def main():
    x, y = map(int, input().split())
    print(gcd(x,y))

if __name__ == "__main__":
    main()

Solution (Python):
import re

def gcd(x, y):
    if x == y:
        return x
    if x < y and y % x == 0:
        return x
    if x > y and x % y == 0:
        return y
    if x <= y:
        m = y % x
        return gcd(x, m)
    if x >= y:
        m = x % y
        return gcd(y, m)

    l = list(range(1, int(min(x, y) / 2) + 1))
    l.reverse()
    r = 1
    
    for i in l:
        if x % i == 0 and y % i == 0:
            return i
    return 1
 
x, y = map(int, re.split(' ', raw_input()))
print(gcd(x, y))

Solution (Python):
import re

def gcd(x, y):
    if x == y:
        return x
    if x < y and y % x == 0:
        return x
    if x > y and x % y == 0:
        return y
    if x <= y:
        m = y % x
        return gcd(x, m)
    if x >= y:
        m = x % y
        return gcd(y, m)

    l = list(range(1, int(min(x, y) / 2) + 1))
    l.reverse()
    r = 1
    for i in l:
        if x % i == 0 and y % i == 0:
            return i
    return 1
 
x, y = map(int, re.split(' ', raw_input()))
print(gcd(x, y))

Solution (Python):
x, y = map(int, input().split())

if x > y:
    larger = x
    smaller = y
else:
    larger = y
    smaller = x

while True:
    quot, rem = divmod(larger, smaller)  
    larger = smaller
    smaller = rem
    if rem == 0:
        gcd = larger
        break

print(gcd)

pass

Solution (Python):

def gcd(x, y):

    if y > x:
        x, y = y, x

    if y == 0:
        return x

    if x >= y:
        return gcd(y, x % y)


x, y = [int(i) for i in input().split()]
print(gcd(x, y))

Solution (Python):
x,y = map(int,input().split())

while True:
    if x >= y:
      x = x % y 
    else:
      y = y % x
    if x % y == 0:
      print(y)
      break
    elif y % x == 0:
      print(x)
      break

Solution (Python):
x,y=map(int, input().split())

def gcd(x,y):
 if x < y:
  x,y = y,x
 while y > 0:
  r = x % y
  x = y
  y = r
 return x

print(str(gcd(x,y)))

Solution (Python):
from fractions import gcd
print(gcd(*list(map(int, input().split(" ")))))

Solution (Python):
x, y = input().split()
x = int(x)
y = int(y)
r = 1
while r > 0:
    if x >= y:
        r = x % y
    else:
        r = y % x

    if r != 0:
        x = y
        y = r
    else:
        print(y)

Solution (Python):
x,y = map(int,input().split())
def gcd(x,y):
    if y == 0:return x
    else:return gcd(y,x%y)

print(gcd(x,y))

Solution (Python):
def main():
    x, y = map(int, input().split(' '))
    print(gcd(x, y))

def gcd(x, y):
    if x < y:
        x, y = y, x

    if x % y == 0:
        return y

    return gcd(y, x%y)

if __name__ == '__main__':
    main()

Solution (Python):


a, b = map(int, input().split())
if a > b:
    big_num = a
    sml_num = b
else:
    big_num = b
    sml_num = a

while True:
    diviser = big_num % sml_num
    if diviser == 0:
        break
    else:
        big_num = sml_num
        sml_num = diviser

print(sml_num)

Solution (Python):


a, b = map(int, input().split())
if a > b:
    big_num = a
    sml_num = b
else:
    big_num = b
    sml_num = a

while True:
    diviser = big_num % sml_num
    if diviser == 0:
        break
    else:
        big_num = sml_num
        sml_num = diviser

print(sml_num)

Solution (Python):
s = input().split(" ")
x = int(s[0])
y = int(s[1])
while x != 0 and y != 0:
    if x >= y:
        x = x % y
    else:
        y = y % x
if x == 0:
    print(y)
else:
    print(x)

Solution (Python):
def eucli(a, b):
    r = a % b
    if r != 0:
        return eucli(b, r)
    else:
        return b

if __name__=="__main__":
    x, y = map(int, input().split())
    print(eucli(x, y))

Solution (Python):
def gcd(x, y):
    if y == 0:
        print(x)
        return x
    return gcd(y, x%y)

x, y = map(int, input().split())
if y > x:
    t = y
    y = x
    x = t
gcd(x, y)

Solution (Python):
import sys

def gcd(a,b):
	temp = a
	if a<b:
		a=b
		b=temp
	if b==0:
		return a
	c = a%b
	return gcd(b,c)


line = sys.stdin.readline().strip().split(" ")
A = int(line[0])
B = int(line[1])

print(gcd(A,B))

Solution (Python):
import sys

def get_gcd(x, y):
    if (x % y == 0) or (y % x == 0):
        return min(x, y)
    return get_gcd((max(x, y) % min(x, y)), min(x, y))

if __name__ == "__main__":
    array = map(lambda x: int(x), sys.stdin.readline().strip().split(" "))
    print get_gcd(array[0], array[1])

Solution (Python):
def gcd(x, y):
    while y != 0:
        temp = x % y
        x = y
        y = temp
    print x

l = map(int, raw_input().split())
gcd(*l)

Solution (Python):


"""
?????§??¬?´???°
??????????????¶??° x, y ?????\?????¨???????????????????????§??¬?´???°????±???????????????°????????????????????????????????????

?????????
??´??° x, y ???????????????x ??\ y ????????° x ??¨ y ????????§??¬?´???°??? y ??¨ x % y ????????§??¬?´???°???????????????
????????§ x % y ??? x ??? y ??§?????£???????????§????????????
"""


x,y = list(map(int,input().strip().split()))
if x < y:
    z = x
    x = y
    y = z

while y > 0:
    z = x % y
    if z == 0:
        print(y)
        break
    x = y
    y = z

Solution (Python):
y,x = sorted([int(s) for s in input().split()])

while y:
	x,y = y,x%y
print(x)

Solution (Python):
def main():
    X, Y = map(int, input().split())

    print(gcd(X, Y))

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

main()

Solution (Python):

def gcd(x, y):
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x = y
        y = r
    return x

print(gcd(*map(int, input().split())))

Solution (Python):
def euclidean_alg(x,y):
    while y:
        x,y=y,x%y
    return x

XY=list(map(int,input().split()))
x=max(XY)
y=min(XY)

print(euclidean_alg(x,y))

Solution (Python):
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n
print(gcd(*map(int, input().split())))

Solution (Python):
x, y = map(int, raw_input().split())
if x < y:
    tmp = y
    y = x
    x = tmp

while 1:
    tmp = x % y
    x = y
    y = tmp
    if tmp == 0:
        tmp = x
        break
print tmp

Solution (Python):
def gcd(a, b):
	while b:
		a, b = b, a%b
	return a
x, y = map(int,input().split())
print(gcd(x, y))

Solution (Python):
x, y = map(int, input().split())
while (1):
    tmp = y
    y = x % tmp
    x = tmp
    if (y==0):
        print(x)
        break

Solution (Python):


import sys, math, os


PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input2.txt", "rt")


def gcd(a, b):
    while b != 0:
       t = b
       b = a % b
       a = t
    return a

x, y = [int(_) for _ in input().split()]
print(gcd(x, y))

Solution (Python):
def division(x,y):
    if y == 0:
        return x
    return division(y, x%y)

x,y=map(int,input().split())

kotae = division(x,y)
print(kotae)

Solution (Python):
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

x, y = map(int, input().split())
print(gcd(x, y))

Solution (Python):
z=list(map(int,input().split()))
z.sort()
a=0

while True:
    if z[1]==z[0]:
        break
    a=z[1]-z[0]
    if z[0]%a==0:
        z[1] = z[0]
        z[0] = a
        z.sort()
        break
    z[1]=z[0]
    z[0]=a
    z.sort()

print(z[0])

Solution (Python):
def gcm(x,y):
    while y:
        x, y = y, x % y
    return x

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

Solution (Python):
a, b = map(int, input().split())
x, y = max(a, b), min(a, b)

while 1:
    if x%y == 0:
        break
    x, y = y, x%y

print(y)

Solution (Python):
def gcd(x, y):
    if x < y:
        x, y = y, x
    while y > 0:
        x, y = y, x % y
    return x

x, y = map(int, input().split())
print(gcd(x, y))

Solution (Python):
from fractions import gcd

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

Solution (Python):
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)


x, y = map(int, raw_input().split())

print gcd(x, y)

Solution (Python):



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

def main():
    X, Y = map(int, input().split())

    print(gcd(X,Y))

if __name__ == "__main__": main()

Solution (Python):
a, b = [int(x) for x in input().split()]
while b:
    a, b = b, a % b
print(a)

Solution (Python):
def gcd(a,b):
	if a < b:
		a,b = b,a
	while b != 0:
		a,b = b,a%b
	return a

a,b = map(int,raw_input().split())
print gcd(a,b)

Solution (Python):
import sys
a1,b1 = list(map(int,input().split()))

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

        return(gcd(a,b))

print(gcd(a1,b1))

Solution (Python):
a = input().split()
x = int(a[0])
y = int(a[1])
while y:
    x, y = y, x%y
print(x)

Solution (Python):
a = input().split()
x = int(a[0])
y = int(a[1])
while y:
    x, y = y, x%y
print(x)

Solution (Python):
num = input().split()
if int(num[0])<int(num[1]):
    x = int(num[1])
    y = int(num[0])
else:
    x = int(num[0])
    y = int(num[1])

end = 0
    
z = x % y
if z == 0:
    print(y)
else:
    while True:
        z1 = y % z
        y1 = z
        if z1 == 0:
            print(z)
            break 
        z = z1
        y = y1

Solution (Python):
a, b = map(int, input().split())

def GCD(a,b):
    x = max(a,b)
    y = min(a,b)   
     
    while y :
        x, y = y, x % y
    return x

print(GCD(a,b))

Solution (Python):
def Euclid(max, min):
    if max % min == 0:
        return min
    else:
        return Euclid(min, max % min)


a, b = map(int, input().split(" "))
if a > b:
    print(Euclid(a, b))
else:
    print(Euclid(b, a))

Solution (Python):
def gcd(a, b): 
    while b: 
        a, b = b, a % b 
    return a 
def lcm(a, b): 
    return a * b // gcd (a, b) 

c,d=[int(i) for i in input().split()]

print(gcd(c,d))

Solution (Python):
x,y = list(map(int,input().split()))

if x < y:
    x,y = y,x

while y>0:
    r = x % y
    x = y
    y = r
    
print(x)

Solution (Python):
x, y = map(int, input().split())
while y > 0:
    x, y = y , x % y
print(x)

Solution (Python):
def gcd(x, y):
    if x < y:
        return gcd(y, x)
    if x%y == 0:
        return y
    else:
        return gcd(y, x%y)

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

Solution (Python):
def getResult(a,b):
	if a<b:
		a,b=b,a
	while b!=0:
		r = a%b
		a = b
		b = r
	return a
a,b = map(int,input().strip().split())
print(getResult(a,b))

Solution (Python):
def swap(x, y):
    tmp = x
    x = y
    y = tmp

def gcm(x, y):
    if x < y:
        swap(x, y)
    while y > 0:
        r = x % y
        x = y
        y = r
    return x

if __name__ == '__main__':
    x, y = list(map(int, input().split()))
    n = gcm(x, y)
    print(n)

Solution (Python):
x, y = map(int, input().split())
while y > 0 :
    x, y = y, x % y
print(x)

Solution (Python):
x, y = map(int, input().split())
while True:
  if x >= y:
    x = x % y
  else:
    y = y % x
  if x % y == 0:
    print(y)
    break
  elif y % x == 0:
    print(x)
    break

Solution (Python):
x , y = map(int,input().split())

def GCD(x,y):
    while y > 0:
        x ,y = y , x %y
    else:
        return x

ans = GCD(x,y)
print(ans)

Solution (Python):
a, b = [int(i) for i in input().split()]

z = 0

def gcd(x,y):
    if x<y:
        z=x
        x=y
        y=z

    while x%y !=0:
        z=x%y
        x=y
        y=z
        gcd(x,y)
    return y

print(gcd(a,b))

Solution (Python):
num = map(int, raw_input().split())

if num[0] > num[1]:
	x = num[0]
	y = num[1]
else:
	y = num[0]
	x = num[1]

while y > 0:
	z = x % y
	x = y
	y = z
print x

Solution (Python):
a,b=sorted(list(map(int, input().split())))

m=b%a
while m>=1:
    b=a
    a=m
    m=b%a
print(a)

Solution (Python):
def main():

    x,y = map(int, input().split())
    while y != 0:
        if x < y: x, y = y, x
        x, y = y, x % y
    print(x)

main()

Solution (Python):

a,b = list(map(int,input().split()))
while 1:
    if a < b:
        a,b = b,a 
    a,b =b, a % b
    if b == 0:
        break    
print (a)

Solution (Python):
a,b=[int(i) for i in input().split(" ")]

while b!=0:
    t = min(a,b)
    b = max(a,b) % min(a,b)
    a = t
print(a)

Solution (Python):
def main() :
    x, y = [int(d) for d in input().split()]
    while y != 0 :
        x, y = y, x%y

    print(x)

if __name__ == '__main__' :
    main()

Solution (Python):
def main() :
    x, y = [int(i) for i in input().split()]
    while y != 0 :
        x, y = y, x%y

    print(x)

if __name__ == '__main__':
    main()

Solution (Python):
dbg = False

a, b = list(map(int, input().split()))

if a > b:
    x, y = a, b
else:
    x, y = b, a

divs = [1]
for i in range(1, int((y+1)/2)+1):
    gcd_tmp = int(y / i)
    if dbg: print('%d, %d' % (i, gcd_tmp))
    if i > gcd_tmp:
        break
    if y % i == 0:
        if x % gcd_tmp == 0:
            print(gcd_tmp)
            exit()
        elif x % i == 0:
            divs.append(i)

print(max(divs))

Solution (Python):
def gcd(a,b): 
    if b == 1:
        return 1
    else:
        return (gcd(b,a%b) if b != 0 else a)
A = list(map(int,input().split()))
print(gcd(A[0],A[1]))

Solution (Python):
def gcd(a, b):
	if a < b:
		tmp = a
		a = b
		b = tmp
	
	r = a % b
	while r != 0:
		a = b
		b = r
		r = a % b

	return b

if __name__ == '__main__':
	l = list(map(int, input().split()))
	x = l[0]
	y = l[1]

	ans = gcd(x, y)
	print(ans)

Solution (Python):
def gcd(X,Y):
    x = X
    y = Y
    if y > x:
        x,y = y,x
    while x % y:
        x,y = y,x%y
    return y

number = [int(i) for i in input().split()]
print(gcd(number[0],number[1]))

Solution (Python):
def main():
    x, y = map(int, input().split())
    print(gcd(x, y))

def gcd(x, y):
    if(x < y):
        x, y = y, x
    while True:
        if(y == 0):
            return x
        else:
            x, y = y, x%y

if __name__ == '__main__':
    main()

Solution (Python):
def greatest_common_divisor(x, y):
    if x < y:
        x, y = y, x

    if y == 0:
        return x
    else:
        return greatest_common_divisor(y, x % y)

if __name__ == '__main__':
    x, y = [int(x) for x in input().split()]
    print(greatest_common_divisor(x, y))

Solution (Python):
N=raw_input()
N = [int(i) for i in N.split()]
m,n = (N[1],N[0]) if N[1] > N[0] else (N[0],N[1])
def gcd(m, n):
    if ((m % n) == 0):
        return n
    else:
        return gcd(n, m % n)
print gcd(m,n)

Solution (Python):
a,b=[int(x) for x in input().split()]

x = max(a,b)
y = min(a,b)
res = y

while x%y>0:
    res = x%y
    x = y
    y = res

print(res)

Solution (Python):
def g(n):
 x,y=n
 r=x%y
 if r>0:g((y,r))
 else:print(y)
g(sorted(list(map(int,input().split()))))

Solution (Python):

def gcd(a,b):
    while b:
        a, b = b, a % b
    return a
n = map(int, raw_input().split())
n.sort(reverse=True)
print gcd(n[0],n[1])

Solution (Python):
ab = [int(x) for x in input().split()]










while True:
    min_i = ab.index(min(ab))
    max_i = ab.index(max(ab))
    r = ab[max_i] % ab[min_i]
    if r == 0:
        print(ab[min_i])
        break
    else:
        ab[max_i] = r

Solution (Python):
import math
a,b=map(int,input().split())
print(math.gcd(a,b))

'''


n=int(input())
r=[int(input())for _ in range(n)]
print(max([max(r[i+1:])-r[i]for i in range(n-1)]))
'''

Solution (Python):
a,b=map(int,input().split())
while b:a,b=b,a%b
print(a)

Solution (Python):
import math
a,b=map(int,input().split())
print(math.gcd(a,b))

'''

a,b=map(int,input().split())
while b:a,b=b,a%b
print(a)
'''

Solution (Python):
import math
a,b=map(int,input().split())
print(math.gcd(a,b))

'''

a,b=map(int,input().split())
while b:a,b=b,a%b
print(a)
'''

Solution (Python):
import math
a,b=map(int,input().split())
print(math.gcd(a,b))

'''

a,b=map(int,input().split())
while b:a,b=b,a%b
print(a)
'''

Solution (Python):
import math
a,b=map(int,input().split())
print(math.gcd(a,b))

'''

a,b=map(int,input().split())
while b:a,b=b,a%b
print(a)
'''

Solution (Python):
import math
a,b=map(int,input().split())
print(math.gcd(a,b))

'''

a,b=map(int,input().split())
while b:a,b=b,a%b
print(a)
'''

Solution (Python):
import math
a,b=map(int,input().split())
print(math.gcd(a,b))

'''

a,b=map(int,input().split())
while b:a,b=b,a%b
print(a)
'''

Solution (Python):
import math
a,b=map(int,input().split())
print(math.gcd(a,b))

Solution (Python):
import math
a,b=map(int,input().split())
print(math.gcd(a,b))

Solution (Python):





import math
a,b=map(int,input().split())
print(math.gcd(a,b))

Solution (Python):
'''
00.02 sec    5588 KB    4 lines     55 bytes
a,b=map(int,input().split())
while b:a,b=b,a%b
print(a)
'''
import math
a,b=map(int,input().split())
print(math.gcd(a,b))

Solution (Python):
'''

a,b=map(int,input().split())
while b:a,b=b,a%b
print(a)
'''

import math
a,b=map(int,input().split())
print(math.gcd(a,b))

Solution (Python):
'''

a,b=map(int,input().split())
while b:a,b=b,a%b
print(a)
'''

import math
a,b=map(int,input().split())
print(math.gcd(a,b))

Solution (Python):
z = input().split()
x = int(z[0])
y = int(z[1])

def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
print(gcd(x,y))

Solution (Python):


import sys

class Algo:
  @staticmethod
  def greatest_common_divisor(x, y):
    while True:
      r = x%y
      if r==0:
        print(y)
        break
      x, y = y, r
l = list(map(int, input().split()))
X = l[0]
Y = l[1]
Algo.greatest_common_divisor(X, Y)

Solution (Python):
x,y = list(map(int,input().split()))


if y>x:x,y = y,x

while x % y !=0:
    x = x%y
    if y>x:x,y = y,x
print(y)

Solution (Python):
def gcd(x, y):
    if x % y != 0:
        return gcd(y, x % y)
    return y

print(gcd(*[int(i) for i in input().split()]))

Solution (Python):
A = list(map(int,input().split()))
a=A[0]
b=A[1]
if a<b:
    a,b=b,a
while b:
    a,b=b,a%b
print(a)

Solution (Python):
A = list(map(int,input().split()))
a=A[0]
b=A[1]
while b:
    a,b=b,a%b
print(a)

Solution (Python):
A = list(map(int,input().split()))
a=A[0]
b=A[1]
while b:
    a, b = b, a%b
print(a)

Solution (Python):
def gcd(a,b):
    if(b):
        return gcd(b,a%b)
    return a

l = raw_input().split()
if(int(l[0]) > int(l[1])):
    print gcd(int(l[0]),int(l[1]))
else:
    print gcd(int(l[1]),int(l[0]))

Solution (Python):
if __name__ == '__main__':
	a, b = input().split()
	a, b = int(a), int(b)
	if a < b:
		x = b
		y = a
	else:
		x = a
		y = b
	while True:
		x, y= y, x % y
		if y == 0:
			print(x)
			break
		else:
			continue

Solution (Python):
x, y = map(int, input().split())
l = max(x, y)
s = min(x, y)

for i in range(x):
    olds = s
    oldl = l
    s = oldl % olds
    l = olds

    if s == 0:
        print(l)
        break

Solution (Python):
def gcd(x, y):
    if x % y == 0:
        return y
    else:
        return gcd(y, x % y)

x, y = map(int, input().split())

print(gcd(x, y))

Solution (Python):
a, b = list(map(int, input().split()))

if a < b:
    a, b = b, a


while True:
    if b == 0:
        break
    tmp = a % b
    a = b
    b = tmp

print(a)

Solution (Python):
from math import *
print(gcd(*map(int, input().split())))