'''
方法1：辗转相除法(欧几里德算法)原理:

假设有两个数x和y，存在一个最大公约数z=(x,y)，即x和y都有公因数z，
因为： 
	x，y都能被z整除；
得：
	x和y的线性组合mx±ny也一定能被z整除。（m和n可取任意整数）

假设： 
	x/y=n余c，
得：
	x=ny+c
	x-ny=c
因为：
	mx±ny能被z整除
得：
	x-ny（作为mx±ny的一个特例）就能被z整除，即x除y的余数c也能被z整除。

因为：
	c，y都能被z整除
得：
	my+nc也能被z整除
	。。。
重复上述步骤，直到余数c=0,最大公约数z=n. 

'''
def divisor(a, b):
    """该函数返回两个数的最大公约数"""
    
    if b == 0:
        return a
    else:
        return divisor(b, a%b)

a, b = input("Enter two natural numbers:").split()
print(divisor(int(a), int(b)))

'''
方法2：更相减损法

假设有两个数x和y，存在一个最大公约数z=(x,y)，即x和y都有公因数z，
因为： 
	x，y都能被z整除；
得：
	当x不等于y时，
	x-y也一定能被z整除
假设： 
	x-y=c，
得：
	c,y都能被z整除（y<x）

重复上述步骤：
当：
	c-y=0时，c为x，y的最大公约数
'''

def divisor(x, y):
    """该函数返回两个数的最大公约数"""

    if x > y:
        c, y = x - y, y
    else:
        c, y = y - x, x

    if c == 0:
        return y

    else:
        return divisor(c, y)


a, b = input("Enter two natural numbers:").split()
print(divisor(int(a), int(b)))



'''
方法3：穷举法
从1开始循环，一直循环到两个数中小的那个数。
'''

def divisor(x, y):
    """该函数返回两个数的最大公约数"""

    # 获取最小值
    if x > y:
        smaller = y
    else:
        smaller = x

    for i in reversed(range(1, smaller + 1)):
        if ((x % i == 0) and (y % i == 0)):
            return i

a, b = input("Enter two natural numbers:").split()
print(divisor(int(a), int(b)))

'''
4. 最小公倍数

最小公倍数 = 用两个数的乘积除以最大公约数

例如x和y的最小公倍数为x*y/gcd（x，y）。（gcd（x，y）表示为两个数的最大公约数）
'''