【算法实践】| 一步步手把手带你实现寻找最小公倍数

作者：迷彩

2022 年 8 月 23 日
广东
本文字数：2039 字
阅读完需：约 7 分钟

前言

其实最小公倍数的概念和计算最小公倍数的方法.那是我们在学习小学数学的时候就已经掌握的数学知识,为了更加通俗易懂一点,本文先从一个'分元宝'的故事入手:

亡故的先父留下遗嘱，
共有遗产 17 个元宝，
老大得元宝的二分之一、 17/2=8.5
老二得元宝的三分之一、 17/3=5.66666
老三得元宝的九分之一、 17/9=1.8
问他们每一个人分别应该分几个元宝？
在《一代大商孟洛川》中是这样做的
孟洛川拿来一个元宝加上去
好了，现在分元宝
答案是：老大 9 个元宝、老二 6 个元宝、老三 2 个元宝。
还剩下一个元宝，是我们孟洛川的，拿回来
很不可思议吧
很简单的初中数学题老大分 1/2,老二分 1/3,老三分 1/9
这三个数的最小公倍数就是 18,即 9/18+6/18+2/18=17/18,就是说他们老爷子给的这个比例和根本就没到 1,。即 1-17/18=1/18,也就是说，直接分，那是分不完 17 元宝的。这样这要用 18 这个最小公倍数就能分开，最后还剩一个

很多人说数学学会四则混合运算就够了.其他买菜又用不到,这不,如果没有数学思维,连财产都分不明白(哈哈哈~),并不是除了四则混合运算其他数学知识没有用,而是你没有学会或者不加以思考.其实很多时候我们在不知不觉中就已经使用了很多数学方法解决生活中所遇到的问题,所以学习数学,除了数学本身,还有数学思维的培养.言归正传,从上面的故事可看出最小公倍数对我们生产生活是有很大帮助的.故事中的例子就是分数的加减法运算在生活中的实际应用

概念

在上篇文章《【算法实践】| 一步步带你实现寻找最大公约数》中我们浅尝了最大公约数的计算,那最大公约数有没有什么联系呢？

最大公约数往往是和最小公倍数成对出现的.最小公倍数（Least Common Multiple，缩写 L.C.M.），如果有一个自然数 a 能被自然数 b 整除，则称 a 为 b 的倍数，b 为 a 的约数，对于两个自然数来说，指该两数共有倍数中最小的一个。计算最小公倍数时，通常会借助最大公约数来辅助计算。

如果一个数既是 a 又是 b 的倍数，那么我们就把这个数叫着 a 和 b 的公倍数，如果这个数在 a b 的所有公倍数里为最小，那这个数就是最小公倍数。

通俗点说，几个数共有的倍数叫做这几个数的公倍数，其中除 0 以外最小的一个公倍数，叫做这几个数的最小公倍数。自然数 a、b 的最小公倍数可以记作[a、b],自然数 a、b 的最大公约数（最大公因数）可以记作(a、b)，当(a、b)=1 时,[a、b]= a×b。如果两个数是倍数关系，则它们的最小公倍数就是较大的数，相邻的两个自然数的最小公倍数是它们的乘积。

简单概括如下：

最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除 0 以外最小的一个公倍数就叫做这几个整数的最小公倍数

最大公约数和最小公倍数二者关系：两个数之积=最小公倍数*最大公约数，这也可作为我们求解最小公倍数的入手点,但是解题时要避免和最大公约数问题混淆

还有另外一个入手点:

因为，素数(质数)是不能被 1 和自身数以外的其它数整除的数；素数 X 的 N 次方，是只能被 X 的 N-1 以下次方，1 和自身数整除．

所以，在求 A，B，C，D，E，…，Z 的最小公倍数时，只需要把这些数分解为素数的 N 次方之间的乘积后，取各素因子的最高次方的乘积，就是这些数的最小公倍数．

适用范围

最小公倍数的适用范围：分数的加减法，中国剩余定理(正确的题在最小公倍数内有解，有唯一的解)

最小公倍数的计算方法

综上所述,求解最小公倍数有一下两种方法:

1.分解质因数法

先把这几个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积，如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数即可。

2.公式法

由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即（a，b）×[a，b]=a×b。所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。

计算流程

1.分解质因数

2.公式法

根据两者的关系,先计算最大公约数,然后使用公式计算最小公倍数

算法实现

1.分解质因数的实现步骤:

输入待求最小公倍数的两个整数 x,y
找出两个整数中较大的一个数字,并记录为 max
使用循环,判断 max 是否可以同时整除 x 和 y,如果可以同时整除.退出循环,将 max 赋值给 Flag,否则 max 加 1,并且继续执行循环直到找到 Flag
返回 Flag,即 x 与 y 的最小公倍数

代码如下:

def LCM(x,y):    if x>y:        max = x
    else:        max = y
    while (True):        if((max % x == 0) and (max % y == 0)):            Flag = max            break        max = max + 1
    return Flag
x = int(input("请输入第一个整数:"))y = int(input("请输入第二个整数:"))
print(x,",", y, "的最小公倍数为:", LCM(x,y))

复制代码

执行结果如下:

2.公式法具体实现步骤:

输入待求最小公倍数的两个整数 x,y
计算两数的乘积 s
计算最大公约数x,y=y,(x%y)
根据公式两个数之积=最小公倍数*最大公约数,计算最小公倍数:s//y
输出最小公倍数

具体实现代码如下:

x = int(input("请输入第一个整数:"))y = int(input("请输入第二个整数:"))s = x * ywhile x % y != 0:    x, y = y, (x % y)else:    print(x, ",", y, "的最大公约数为:",y)    print(x, ",", y, "的最小公倍数为:",s // y)

复制代码

执行结果如下: