Python求两数最大公约数

最大公约数

        最大公公约数，也称最大因数、最大公因子，指几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。例：6和9，有公约数1,3，其中3为6和9的最大公约数。

解决思路

        使用两个列表分别存储两数的约数，最后再取出两列表中相同数的最大值，该数为最大公约数。

源码

def getMax_Com():
    buf_1 = []#用于存储范围内相乘等于num_1的数
    buf_2 = []#用于存储范围内相乘等于num_2的数
    num_1 = int(input("请输入第一个整数:"))
    num_2 = int(input("请输入第二个整数:"))
    if num_1 == num_2:#输入的数相同，没有判断的意义，因为结果为本身
        print("最大公约数为:", num_1)
        return 0
    elif num_1 > num_2:#最大公约数最大不会超过最小的那个数，取最小的比较范围
        for temp_1 in range(1, num_2+1):
            for temp_2 in range(temp_1, num_2+1):
                result_1 = temp_1 * temp_2
                if result_1 == num_2:#存储num_2约数
                    buf_1.append(temp_1)
                    buf_1.append(temp_2)
                elif result_1 == num_1:#存储小于num_2范围内的num_1约数
                    buf_2.append(temp_1)
                    buf_2.append(temp_2)
    else:
        for temp_1 in range(1, num_1+1):
            for temp_2 in range(temp_1, num_1+1):
                result_1 = temp_1 * temp_2
                if result_1 == num_1:#存储约数
                    buf_1.append(temp_1)
                    buf_1.append(temp_2)
                elif result_1 == num_2:#存储约数
                    buf_2.append(temp_1)
                    buf_2.append(temp_2)
    result_2 = 0
    for temp_3 in buf_1:#比较两列表中相等的数取最大值
        for temp_4 in buf_2:
            if temp_4 == temp_3:
                if temp_3 > result_2:
                    result_2 = temp_3
    print("最大公约数为:", result_2)
getMax_Com()

运行结果