首页 > 编程笔记

Python求最小公倍数(2种实现方案)

求任意两个正整数的最小公倍数(Least Common Multiple,LCM)。

问题分析

如果有一个自然数 a 能被自然数 b 整除,则称 a 为 b 的倍数,b 为 a 的约数,对于两个整数来说,最小公倍数是指这两个数共有倍数中最小的一个。计算最小公倍数时,通常会借助最大公约数来辅助计算,即最小公倍数=两数的乘积/最大公约(因)数,解题时要避免和最大公约(因)数问题混淆。

对于最小公倍数的求解,除了利用最大公约数外还可根据定义进行算法设计。要求任意两个正整数的最小公倍数,就是求出一个最小的能同时被两个整数整除的自然数。

第一种实现方案

根据定义可知,两个整数的最小公倍数不小于两数中的任意一个,若大数不是小数的倍数,则可由大数开始利用递增的方法找到第一个满足条件的数。利用定义求最小公倍数的关键是找到两个整数中较大的数。

对于输入的两个正整数 m 和 n,每次输入的大小顺序可能不同,为了使程序具有一般性,首先对整数 m 和 n 进行大小排序,规定变量 m 中存储大数、变量 n 中存储小数。

若输入的两个数,大数 m 是小数 n 的倍数,那么大数 m 即为所求的最小公倍数;若大数 m 不能被小数 n 整除,则需要寻找一个能同时被两数整除的自然数,即从大数 m 开始依次向后递增直到找到第一个能同时被两数整除的数为止,故循环变量 i 的初值为 m。需要注意的是,在找到第一个满足条件的 i 值后,循环没必要继续进行,故用 break 来结束循环。

对应代码为:
if __name__ == "__main__":
    print("请输入两个整数")
    m = int(input("m = "))
    n = int(input("n = "))
    if m < n: # 比较两个数的大小,使得m中存储大数,n中存储小数
        temp = m
        m = n
        n = temp
    i = m
    while i > 0: # 从大数开始寻找满足条件的自然数
        if i % m == 0 and i % n == 0:
            # 输出满足条件的自然数并结束循环
            print("%d 和 %d 的最小公倍数为:%d" %(m, n, i))
            break
        i += 1
运行过程为:

请输入两个整数
m = 4
n = 5
5 和 4 的最小公倍数为:20

第二种实现方案

最小公倍数不可以像最大公约数那样直接利用辗转相除法求出,但可以借助辗转相除法求得的最大公约数来求最小公倍数。

在已知最大公约数的情况下,借助公式最小公倍数=两数的乘积/最大公约(因)数,即可求出两整数的最小公倍数。

对应代码如下:
if __name__ == "__main__":
    print("请输入两个整数")
    m = int(input("m = "))
    n = int(input("n = "))
    k = m * n # k存储两数的乘积
    print("%d 和 %d 的最小公倍数为: " %(m, n), end="")
    if m < n: # 比较两个数的大小,使得m存储大数,n存储小数
        temp = m
        m = n
        n = temp
    b = m % n # b存储m除以n的余数
    while b != 0:
        m = n # 原来的小数作为下次运算时的大数
        n = b # 将上一次的余数作为下次相除时的小数
        b = m % n
    resultNum = k // n # 两数乘积除以最大公约数即为它们的最小公倍数
    print("%d" %resultNum)
运行结果为:

请输入两个整数
m = 4
n = 5
4 和 5 的最小公倍数为: 20

推荐阅读

副业交流群 关注微信公众号,加入副业交流群,学习变现经验,交流各种打法。