异常教程

Python 最小公倍数算法（手把手讲解）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战(已更新的所有项目都能学习) / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

  • 新开坑项目:《Spring AI 项目实战》 正在持续爆肝中，基于 Spring AI + Spring Boot 3.x + JDK 21...， 点击查看 ;
  • 《从零手撸：仿小红书（微服务架构）》 已完结，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;
  • 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

在编程与数学问题解决中，最小公倍数算法（LCM, Least Common Multiple）是一个基础但极其重要的工具。无论是处理日程安排、工程计算，还是优化代码逻辑，理解如何高效计算两个或多个整数的最小公倍数，都能显著提升问题解决的效率。Python 作为一门简洁且功能强大的编程语言，提供了多种实现 LCM 的方法，从基础的循环遍历到基于数学定理的优化算法，都能帮助开发者快速达成目标。本文将从零开始，逐步解析 LCM 的原理、算法实现及优化策略，并结合实际案例，帮助读者掌握这一核心技能。

LCM 的基本概念：从数学到编程

什么是最小公倍数？

最小公倍数（LCM）是指两个或多个整数的公共倍数中最小的一个正整数。例如，数字 4 和 6 的倍数分别为：

  • 4 的倍数：4, 8, 12, 16, 20, 24,…
  • 6 的倍数：6, 12, 18, 24,…
    它们的最小公倍数是 12。

LCM 与 GCD 的关系

最小公倍数的计算与最大公约数（GCD, Greatest Common Divisor）密切相关。数学上，LCM 可通过以下公式与 GCD 直接关联：
LCM(a, b) = (a × b) / GCD(a, b)

这一公式的意义在于：GCD 越大，LCM 越小，因为 GCD 是两个数的最大共同因数，因此 LCM 的结果会因共同因数的存在而“压缩”。例如，4 和 6 的 GCD 是 2，因此 LCM = (4×6)/2 = 12。

为什么需要计算 LCM？

在编程中，LCM 常用于以下场景：

  • 日程安排：例如，两个人每周三和周五分别有空，求他们下次同时有空的日期。
  • 工程问题：例如，齿轮的齿数设计需满足啮合条件，避免因齿数比例不合理导致的磨损。
  • 算法优化：例如，在循环中寻找周期性问题的同步点。

算法原理与实现：从基础到优化

方法一：直接遍历法（Brute Force）

这是最直观的 LCM 计算方法：从较大的数开始，逐个检查是否能同时被两个数整除。

实现步骤：

  1. 确定两个数 a 和 b。
  2. 从较大的数开始，依次检查是否能被 a 和 b 同时整除。
  3. 第一个满足条件的数即为 LCM。

代码示例：

def lcm_brute_force(a, b):  
    max_num = max(a, b)  
    while True:  
        if max_num % a == 0 and max_num % b == 0:  
            return max_num  
        max_num += 1  

print(lcm_brute_force(4, 6))  # 输出 12

优缺点分析：

  • 优点：逻辑简单，容易理解。
  • 缺点：当输入数值较大时（如 1e6 和 1e6+1），循环次数可能达到上亿次，效率极低。

方法二：基于 GCD 的欧几里得算法

通过 欧几里得算法（Euclidean Algorithm）高效计算 GCD，再利用公式 LCM(a,b) = (a × b) // GCD(a,b) 得到 LCM。

欧几里得算法的核心思想：

  • 辗转相除法：用较大的数除以较小的数，取余数；然后用较小的数和余数继续相除，直到余数为零。最后的非零除数即为 GCD。

代码实现：

def gcd_euclidean(a, b):  
    while b != 0:  
        a, b = b, a % b  
    return a  

def lcm_euclidean(a, b):  
    return (a * b) // gcd_euclidean(a, b)  

print(lcm_euclidean(4, 6))  # 输出 12

优缺点分析：

  • 优点：时间复杂度低（O(log(min(a,b)))），适用于大数场景。
  • 缺点：需要先理解 GCD 的计算逻辑。

方法三：使用 Python 标准库 math.gcd

Python 3.5+ 的 math 模块提供了内置的 gcd 函数，可直接计算 LCM：

代码示例：

import math  

def lcm_math(a, b):  
    return (a * b) // math.gcd(a, b)  

print(lcm_math(4, 6))  # 输出 12

注意事项：

  • 若输入为负数，需先取绝对值：math.gcd(-4, 6) 返回 2，但 LCM 应始终为正数。

方法四：Python 3.9+ 的 math.lcm

从 Python 3.9 开始，math 模块新增了 lcm 函数，支持直接计算多个数的 LCM：

代码示例：

import math  

print(math.lcm(4, 6, 8))  # 输出 24（4、6、8 的 LCM）

优势：

  • 支持多参数输入，简化代码复杂度。

算法性能对比与选择建议

以下表格对比了不同方法的性能特点：

方法名称时间复杂度适用场景
直接遍历法O(n)小数值或教学演示场景
欧几里得算法O(log n)大数值或需要高效计算的场景
Python math.gcdO(log n)推荐通用场景，代码简洁
Python math.lcm (3.9+)O(n)需要计算多个数的 LCM 时最优

实际案例与应用

案例 1：日程安排

假设两人分别每 3 天和 5 天见面一次，求他们下一次共同有空的天数：

import math  

def next_meeting_day(days_a, days_b):  
    return math.lcm(days_a, days_b)  

print(next_meeting_day(3, 5))  # 输出 15

案例 2：工程齿轮设计

设计两个齿轮的齿数，使其能同步转动且 LCM 为 60：

print(math.lcm(12, 15))  # 输出 60

扩展思考：多参数 LCM 的计算

对于多个数的 LCM，可通过循环两两计算：

def lcm_multiple(numbers):  
    lcm_result = 1  
    for num in numbers:  
        lcm_result = math.lcm(lcm_result, num)  
    return lcm_result  

print(lcm_multiple([4, 6, 8]))  # 输出 24

结论

Python 最小公倍数算法的实现方法多样，开发者需根据场景选择最优方案：

  • 教学或小数据场景：直接遍历法便于理解。
  • 高效计算需求：欧几里得算法或 math.gcd 是首选。
  • Python 3.9+ 环境：直接使用 math.lcm 简化代码。

掌握 LCM 的计算不仅能解决数学问题，还能为算法优化和工程实践提供强大工具。随着 Python 版本的迭代，开发者应持续关注标准库的新特性，以提升代码的简洁性和效率。

最新发布

查看更多文章