100个python算法超详细讲解：最小公倍数

1．问题描述
求任意两个正整数的最小公倍数（Least Common Multiple，
LCM）。
2．问题分析
如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约
数，对于两个整数来说，最小公倍数是指这两个数共有倍数中最小的
一个。计算最小公倍数时，通常会借助最大公约数来辅助计算，即最
小公倍数=两数的乘积/最大公约（因）数，解题时要避免和最大公约
（因）数问题混淆。
对于最小公倍数的求解，除了利用最大公约数外还可根据定义进
行算法设计。要求任意两个正整数的最小公倍数，就是求出一个最小
的能同时被两个整数整除的自然数。
3．算法设计
根据定义可知，两个整数的最小公倍数不小于两数中的任意一
个，若大数不是小数的倍数，则可由大数开始利用递增的方法找到第
一个满足条件的数。利用定义求最小公倍数的关键是找到两个整数中
较大的数。
对于输入的两个正整数m和n，每次输入的大小顺序可能不同，为
了使程序具有一般性，首先对整数m和n进行大小排序，规定变量m中
存储大数、变量n中存储小数。
若输入时m的值小于变量n的值，则需要交换两个变量中存储的内
容。再次强调，交换两个变量中的内容并不是简单地相互赋值，而要
借助中间变量，将其中一个变量的值暂存（防止在交换过程中将原来
的内容丢失）。此过程在4.4节及第1章1.8节中已介绍过，这里不再赘
述。

比较两个数的大小 使得 中存储大数 中存储小数
if m < n: # 比较两个数的大小，使得m中存储大数，n中存储小数
temp = m
m = n
n = temp

若输入的两个数，大数m是小数n的倍数，那么大数m即为所求的
最小公倍数；若大数m不能被小数n整除，则需要寻找一个能同时被两
数整除的自然数，即从大数m开始依次向后递增直到找到第一个能同时
被两数整除的数为止，故循环变量i的初值为m。需要注意的是，在找
到第一个满足条件的i值后，循环没必要继续进行，故用break来结束循
环。
在上面的分析过程中没有提到循环变量的终止条件，因i的最大值
不能确定，像这种终止条件不确定的情况如何来表示呢？方法有两
种，第一，可以把判定条件表示成循环变量满足的基本条件，如本例
终止条件可表示成i>0；第二，终止条件省略不写，利用循环体中的语
句结束循环，如在找到第一个满足条件的自然数时利用break语句结束
循环。

i = m
while i > 0: # 从大数开始寻找满足条件的自然数
if i % m == 0 and i % n == 0:
# 输出满足条件的自然数并结束循环
print("%d 和 %d 的最小公倍数为：%d" %(m, n, i))
break
i += 1

通常情况下，如果我们知道循环的次数，可以使用for循环来实
现；如果不清楚循环的次数，可以使用while循环来实现，while循环的
条件就是循环的终止条件。
4．确定程序框架
程序流程图如图4.11所示。

 5．完整的程序
根据上面的分析，编写程序如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 最小公倍数
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

最小公倍数不可以像最大公约数那样直接利用辗转相除法求出，
但可以借助辗转相除法求得的最大公约数来求最小公倍数。辗转相除
法求最大公约数的代码在4.4节中已经给出，在已知最大公约数的情况
下，借助公式最小公倍数=两数的乘积/最大公约（因）数，即可求出两
整数的最小公倍数。
由4.4节中求解最大公约数的代码可知，在辗转相除的过程中，变
量m、n的值是一直在变化的，程序结束时与最初输入的值已不同，但
在求最小公倍数时要用到两变量初值的乘积，因此在进入循环进行辗
转相除之前应先将两变量的乘积保存，假设存储到变量k中，根据公式
用变量k的值除以求得的最大公约数n得到的值即为所求的最小公倍
数。对应代码如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 最小公倍数——利用两数的最大公约数求出最小公倍数
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)

当然，根据定义求得的最大公约数，也可由公式最小公倍数=两数
的乘积/最大公约（因）数，再次求出最小公倍数。方法同上述代码。
6．运行结果
在PyCharm下运行程序，屏幕上提示“请输入两个整数”，输入45和
63后，结果为315，如图4.12a所示；输入4和5后，结果为20，如图
4.12b所示。