【蓝桥杯每日一练：递归算法求两个数的最大公约数】

问题描述

求最大公约数问题。

输入格式

输入一行，包含两个正整数(<1,000,000,000)。

输出格式

输出一个正整数，即这两个正整数的最大公约数。

输入样例

6 9

输出样例

3

代码

n,m=map(int,input().split())
if n==m:
    print(n)
else:
    if n>m:
        a=n
        n=m
        m=a
    while True:
        x=m-n
        if (n%x==0 or m%x==0):
            print(x)
            break
        else:
            m=x
            if n > m:
                a = n
                n = m
                m = a