求最小公倍数算法汇总

《求最小公倍数算法汇总》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、最小公倍数（LeastCommonMultiple，缩写L.C.M.），如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数，对于两个整数来说，指该两数共有倍数中最小的一个。计算最小公倍数时，通常会借助最大公约数来辅助计算。其中，4是最小的公倍数，叫做他们的最小公倍数。例如，十天干和十二地支混合称呼一阴历年，干支循环回归同一名称的所需时间，就是12和10的最小公倍数，即是60──一个“甲子”。对分数进行加减运算时，要求两数的分母相同才能计算，故需要通分；假如令两个分数的分母通分成最小公倍数，计算量便最低。目录最小公

2、倍数的求法专题简析计算机程序实现最小公倍数的求法短除法　　步骤：　　一、找出两数的最小公约数，列短除式，用最小公约数去除这两个数，得二商；　　二、找出二商的最小公约数，用最小公约数去除二商，得新一级二商；　　三、以此类推，直到二商为互质数；　　四、将所有的公约数及最后的二商相乘，所得积就是原二数的最小公倍数。　　例：求48和42的最小公倍数　　解：48与42的最小公约数为2　　48/2=24；42/2=21；24与21的最小公约数为3　　24/3=8；21/3=7；8和7互为质数　　2×3×8×7=336　　短除法是最常见的用法

3、。也有其他的方法，再用短除法是一定要超出他们的最大公倍数。质因数分解　　举例：12和27的最小公倍数　　12=2×2×3　　27=3×3×3　　必须用里面数字中的最大次方者，像本题有3和3的立方，所以必须使用3的立方(也就是3*3*3)，不能使用3　　所以：　　2×2×3×3×3=4×27=108　　两数的最小公倍数是108借助最大公约数求最小公倍数　　步骤：　　一、利用辗除法或其它方法求得最大公约数；　　二、最小公倍数等于两数之积除以最大公约数。　　举例：12和8的最大公约数为4　　12×8/4=24　　两数的最小公倍数是24

4、专题简析　　几个数公有的倍数叫做这几个数的公倍数，其中最小的一个公倍数，叫做这几个数的最小公倍数。自然数a、b的最小公倍数可以记作[a、b]，自然数a、b的最大公因数可以记作(a、b），当（a、b）=1时，[a、b]=a×b。　　两个数的最大公因数和最小公倍数有着下列关系：　　最大公因数×最小公倍数=两数的乘积　　即（a、b）×[a、b]=a×b　　要解答求最小公倍数的问题，关键要根据题目中的已知条件，对问题作全面的分析，若要求的数对已知条件来说，是处于被除数的地位，通过就是求最小公倍数，解题时要避免和最大公约数问题混淆。例题1

5、　　两个数的最大公因数是15，最小公倍数是90，求这两个数分别是多少？　　分析根据“两个数的最大公因数与最小公倍数的乘积等于这两个数的乘积（这里应该写错了吧？90/15=6，根据下面的解答应该是这个意思）”可先求出这两个数的乘积，再把这个积分解成两个数。根据题意：　　当a1b1分别是1和6时，a、b分别为15×1=15，15×6=90；当a1b1分别是2和3时，a、b分别为15×2=30，15×3=45。所以，这两个数是15和90或者30和45。　　练习一　　1，两个数的最大公因数是9，最小公倍数是90，求这两个数分别是多少？　

6、　2，两个数的最大公因数是12，最小公倍数是60，求这两个数的和是多少？　　3，两个数的最大公因数是60，最小公倍数是720，其中一个数是180，另一个数是多少？例题2　　两个自然数的积是360，最小公倍数是120，这两个数各是多少？　　分析我们把这两个自然数称为甲数和乙数。因为甲、乙两数的积一定等于甲、乙两数的最大公因数与最小公倍数的积。根据这一规律，我们可以求出这两个数的最大公因数是360÷120=3。又因为（甲÷3=a，乙÷3=b）中，3×a×b=120，a和b一定是互质数，所以，a和b可以是1和40，也可以是5和8。当a

7、和b是1和40时，所求的数是3×1=3和3×40=120；当a和b是5和8时，所求的数是3×5=15和3×8=24。　　练习二　　1，求36和24的最大公因数和最小公倍数的乘积。　　2，已知两个数的积是3072，最大公因数是16，求这两个数。　　3，已知两个数的最大公因数是13，最小公倍数是78，求这两个数的差。例题3　　甲、乙、丙三人是朋友，他们每隔不同天数到图书馆去一次。甲3天去一次，乙4天去一次，丙5天去一次。有一天，他们三人恰好在图书馆相会，问至少再过多少天他们三人又在图书馆相会？　　分析从第一次三人在图书馆相会到下一次

8、再次相会，相隔的天数应该是3、4、5的最小公倍数。因为3、4、5的最小公倍数是60，所以至少再过60天他们三人又在图书馆相会。　　练习三　　1，1路、2路和5路车都从东站发车，1路车每隔10分钟发一辆，2路车每隔15分钟发一辆，而5路车每隔20分钟发一辆。当这三