最大公约数

gzj137070928

计算两个数的最大公约数

def gcd(x, y):
    '''该函数返回两个数的最大公约数'''
    if not(x > 0 and y > 0):
        print("Invalid numbers!")
    # 用匿名函数简化构造取较小值的函数
    smaller = lambda x,y: x if x < y else y
    for i in range(1, smaller(x, y) + 1):
        if (x % i == 0) and (y % i == 0):
            gcd = i
    return gcd


num1 = int(input('请输入第一个数字：'))
num2 = int(input('请输入第二个数字：'))
print(num1, '和', num2, '的最大公约数是：', gcd(num1, num2))

嘉岳呀

我上周六刚学的最大公约数和最小公倍数

gzj137070928

嘉岳呀 发表于 2020-10-14 18:39
我上周六刚学的最大公约数和最小公倍数

还有简洁版：利用欧几里得算法
思想简介：(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等

def gcd2(x, y):
    while y:
        t = x % y
        x = y
        y = t
    return x


print(gcd2(4, 6))