Python - 求两数的最大公约数与最小公倍数

一.引言

最大公约数 Greatest Common Divisor ，指两个或多个整数共有约数中最大的一个

最小公倍数 Least Common Multiple，指两个或多个整数公有的倍数中最小的一个

二.最大公约数 GCD

最大公约数一定小于等于两数中较小的 num，所以遍历 1- smaller 里所有的数字。

def gcd(x, y):
    _gcd = 1
    if x > y:
        smaller = y
    else:
        smaller = x
    for i in range(1, smaller + 1):
        if (x % i == 0) and (y % i == 0):
            _gcd = i
    return _gcd

三.最小公倍数 LCM

最小公倍数寻找第一个满足整除两数字为0的数字即可，最小公倍数一定大于等于两个 num，所以从二者较大的数字开始遍历，又因为是求最小，所以一旦遍历到满足条件的数字则 break 退出循环。

def lcm(x, y):
    _lcm = x * y
    if x > y:
        greater = x
    else:
        greater = y
    while True:
        if (greater % x == 0) and (greater % y == 0):
            _lcm = greater
            break
        greater += 1
    return _lcm

四.测试

上面两个是最基础的实现，还有一些效率更高的方法有空可以再梳理一下。

num1 = 36
num2 = 100
print("第一个数字为: %d" % num1)
print("第二个数字为: %d" % num2)
print("最大公约数为", gcd(num1, num2), "最小公倍数为", lcm(num1, num2))

第一个数字为: 36
第二个数字为: 100
最大公约数为 4 最小公倍数为 900