题解 | #求最小公倍数#
求最小公倍数
https://www.nowcoder.com/practice/22948c2cad484e0291350abad86136c3
最小公倍数 = 两数之积除以最大公约数
最小公倍数和最大公约数算法以下四种：
方法一：暴力法
a, b = map(int, input().split()) gcd = 1 for i in range(2, min(a, b) + 1): if a % i == 0 and b % i == 0: gcd = i print(a * b // gcd)
方法二：短除法
a, b = map(int, input().split()) tmp = 1 for i in range(2, min(a, b) + 1): while a % i == 0 and b % i == 0: # 逐一找出公共除数 tmp *= i a //= i b //= i print(tmp * a * b)
方法三：辗转相除法（非递归）
def lcm(a, b): # 最小公倍数 while a % b: a, b = b, a % b return b while True: try: a, b = map(int, input().split()) print(int(a * b / lcm(a, b))) # 最小公倍数 = 两数之积/最大公约数 except: break
方法四：辗转相除法（递归）
def gcd(a, b): if b == 0: # base case return a else: return gcd(b, a % b) while True: try: a, b = map(int, input().split()) print(a * b // gcd(a, b)) # 最小公倍数 = 两数之积/最大公约数；注意整除 except: break
查看5道真题和解析