猫史档案馆

【问题】

把分数化成最简分数的过程就叫约分。如24/30进行约分以后就是4/5。如果这个分数的分子和分母较大，对它进行约分往往不是一件容易的事情。但是，你可以编写一个程序来完成这个工作。

【测试用例】

输入

分子4，分母8

分子18，分母81

分子23，分母46

输出

分子1，分母2

分子2，分母9

分子1，分母2

当输入一个分数的分子和分母后，程序会输出约分后的分数的分子和分母。

【思路】

约分其实可以找到分子和分母的最大公约数，然后分子和分母同时除以最大公约数，即可得到结果。求两个数的最大公约数可以用辗转相除法，然后递归调用函数即可返回最大公约数。

【注释】

辗转相除法，又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

【代码】

def euclidean(a, b):
    if not b:
        return a
    return euclidean(b, a % b)


if __name__ == '__main__':
    m = int(input("分子："))
    n = int(input("分母："))

    a = m if m > n else n
    b = m if m < n else n

    r = euclidean(a, b)
    # print(r)
    print("分子：" + str(m // r) + "，" + "分母：" + str(n // r))