如何在Python中不使用math库和自定义函数求1到n的最小公倍数

核心思路 #

• 逐次迭代计算当前最小公倍数与下一个整数的最小公倍数，两个整数a、b的最小公倍数计算公式为 a * b // 两数的最大公约数(GCD)
• 不依赖math库的前提下，直接用辗转相除法计算GCD，无需额外定义函数，逻辑直接嵌入主循环即可

实现代码 #

n = int(input())
lcm_result = 1
for i in range(2, n + 1):
    # 用辗转相除法计算当前lcm和i的GCD
    a, b = lcm_result, i
    while b != 0:
        a, b = b, a % b
    gcd_val = a
    # 更新最小公倍数
    lcm_result = lcm_result * i // gcd_val
print(lcm_result)

代码说明 #

• 输入的正整数n会被转换为整数类型
• 初始lcm_result设为1，因为1和任意整数的最小公倍数都是该整数本身
• 遍历区间[2, n]的所有整数：
  • 用临时变量a、b分别存储当前的最小公倍数和当前遍历的整数i
  • 辗转相除循环：只要b不为0，就把b赋值给a，把a % b的结果赋值给b，循环结束时a就是两者的最大公约数
  • 用LCM公式更新lcm_result的值
• 遍历结束后输出的lcm_result就是能被[1,n]所有整数整除的最小整数

测试示例 #

• 输入10，输出2520
• 输入5，输出60
• 输入20，输出232792560

内容的提问来源于stack exchange，提问作者curious