博客

2.最小公倍数/最大公约数

Type one: 2个数

"""
最大公约数
Author:Anderson
Time:2020-11-4
"""
def gcd(a,b):
    if a<b:
        a,b=b,a
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

思路分析：求两个数的最大公约数，可以用欧几里得算法（辗转相除法。）其基于的定理是：两个数的最大公约数等于较小的那个数和这两个数相除的余数的最大公约数

"""
最小公倍数
Author:Anderson
Time:2020-11-4
"""
def lcm(a, b):
    if a * b == 0:
        return 0
    else:
        return int(a * b / gcd(a, b))

这里用了计算公式 lcm(a,b)=a

b/gcd(a,b)

*

Type two: 多个数

"""
最大公约数
Author:Anderson
Time:2020-11-4
"""
def gcd2(*args):
    res=gcd(gcd(args[0],args[1]))
    for i in range(2,len(args)):
        res=gcd(res,args[i])
    return res

#思路分析：
gcd(a,b,c)=gcd(gcd(a,b),c)


"""
最小公倍数
Author:Anderson
Time:2020-11-4
"""
def lcm2(*args):
    res=lcm(args[0],args[1])
    for i in range(2,len(args)):
        res=lcm(res,args[i])
    return res

#*args是指输入的数据类型是tuple