上一篇
Python编程教程：求最大公约数和最小公倍数的算法详解 | Python算法学习
Python求最大公约数和最小公倍数算法详解
在数学和编程中，最大公约数（GCD）和最小公倍数（LCM）是两个基础而重要的概念。本教程将详细介绍在Python中计算GCD和LCM的多种算法实现。
基本概念
最大公约数（GCD）
最大公约数（Greatest Common Divisor）是指两个或多个整数共有约数中最大的一个。例如，12和18的最大公约数是6。
最小公倍数（LCM）
最小公倍数（Least Common Multiple）是指两个或多个整数公有的倍数中最小的一个。例如，4和6的最小公倍数是12。
计算最大公约数的算法
1. 欧几里得算法（辗转相除法）
这是计算GCD最高效的方法之一，基于原理：gcd(a, b) = gcd(b, a mod b)
# 欧几里得算法实现
def gcd_euclidean(a, b):
while b != 0:
a, b = b, a % b
return a
示例：
计算 gcd(48, 18)
步骤1: 48 ÷ 18 = 2 余 12 → gcd(18, 12)
步骤2: 18 ÷ 12 = 1 余 6 → gcd(12, 6)
步骤3: 12 ÷ 6 = 2 余 0 → gcd(6, 0)
结果: 6
2. 更相减损法
中国古代的算法，基于原理：gcd(a, b) = gcd(b, a-b)（当a>b）
# 更相减损法实现
def gcd_subtraction(a, b):
if a == b:
return a
if a < b:
a, b = b, a
return gcd_subtraction(b, a - b)
示例：
计算 gcd(48, 18)
步骤1: gcd(48, 18) → gcd(18, 30) [48-18=30]
步骤2: gcd(30, 18) → gcd(18, 12) [30-18=12]
步骤3: gcd(18, 12) → gcd(12, 6) [18-12=6]
步骤4: gcd(12, 6) → gcd(6, 6) [12-6=6]
结果: 6
计算最小公倍数的算法
利用GCD计算LCM是最有效的方法：lcm(a, b) = abs(a * b) / gcd(a, b)
# 使用欧几里得算法计算LCM
def lcm(a, b):
return abs(a * b) // gcd_euclidean(a, b)
示例：
计算 lcm(12, 18)
gcd(12, 18) = 6
lcm(12, 18) = (12 × 18) / 6 = 216 / 6 = 36
Python内置方法
Python的math模块提供了计算GCD的内置函数：
import math
# 使用math.gcd()
gcd_value = math.gcd(48, 18) # 返回6
# 计算LCM（Python 3.9+）
lcm_value = math.lcm(12, 18) # 返回36
# 对于Python 3.9以下版本
def lcm(a, b):
return abs(a * b) // math.gcd(a, b)
算法比较
| 算法 | 时间复杂度 | 优点 | 缺点 |
|---|---|---|---|
| 欧几里得算法 | O(log(min(a,b))) | 效率高，适合大数 | 使用取模运算 |
| 更相减损法 | O(max(a,b)) | 不使用取模运算 | 效率低，特别是数字相差大时 |
| math.gcd() | O(log(min(a,b))) | 内置实现，效率最高 | 依赖Python版本 |
实际应用场景
分数化简
使用GCD化简分数到最简形式：16/24 → 2/3
周期事件同步
计算两个周期事件同时发生的最小时间间隔（LCM）
密码学
RSA等加密算法中大量使用GCD计算
GCD和LCM计算器
注意：
1. 所有算法都要求输入为正整数
2. 对于多个数的GCD/LCM，可以迭代应用：gcd(a,b,c) = gcd(gcd(a,b),c)
3. 实际编程中推荐使用math模块中的函数
本文由DuZhuo于2025-07-22发表在吾爱品聚，如有疑问，请联系我们。
本文链接：https://www.521pj.cn/20256237.html
发表评论