python中求最大公约数的三种方法-Python教程-PHP中文网

python中求最大公约数的三种方法

冰川箭仙

发布： 2025-11-25 21:03:06

原创

471人浏览过

答案是三种求最大公约数的方法：math.gcd()函数最简便，欧几里得算法高效且经典，更相减损术直观但较慢，适合教学。

python中求最大公约数的三种方法

在 Python 中求最大公约数（GCD，Greatest Common Divisor）有多种方法，以下是三种常用且实用的方式，每种都有其适用场景和实现逻辑。

1. 使用内置 math.gcd() 函数

Python 标准库中的 math 模块提供了 gcd() 函数，是最简单直接的方法。

从 Python 3.5 开始，math.gcd() 可直接使用；在 3.9 之后还支持多个参数。

优点：代码简洁，性能好，经过优化
缺点：只能处理整数，不能自定义算法逻辑

示例代码：

立即学习“Python免费学习笔记（深入）”；

import math<br>result = math.gcd(48, 18)<br>print(result)  # 输出 6

登录后复制

2. 使用欧几里得算法（辗转相除法）

这是数学上经典的求 GCD 方法，基于原理：gcd(a, b) = gcd(b, a % b)，直到余数为 0。

适合理解算法本质
可以用循环或递归实现

递归实现：

def gcd(a, b):<br>    if b == 0:<br>        return a<br>    return gcd(b, a % b)<br><br>print(gcd(48, 18))  # 输出 6

登录后复制

最优化方法的Matlab实现中文WORD版

用最优化方法解决最优化问题的技术称为最优化技术，它包含两个方面的内容： 1）建立数学模型即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。 2）数学求解数学模型建好以后，选择合理的最优化方法进行求解。利用Matlab的优化工具箱，可以求解线性规划、非线性规划和多目标规划问题。具体而言，包括线性、非线性最小化，最大最小化，二次规划，半无限问题，线性、非线性方程（组）的求解，线性、非线性的最小二乘问题。另外，该工具箱还提供了线性、非线性最小化，方程求解，

查看详情

循环实现（更节省内存）：

def gcd(a, b):<br>    while b:<br>        a, b = b, a % b<br>    return a

登录后复制

3. 使用更相减损术（辗转相减法）

这是中国古代《九章算术》中的方法，基于原理：两个数的最大公约数等于它们的差与较小数的 GCD。

思想直观，但效率低于欧几里得算法
适合教学理解

实现方式：

def gcd(a, b):<br>    while a != b:<br>        if a > b:<br>            a -= b<br>        else:<br>            b -= a<br>    return a<br><br>print(gcd(48, 18))  # 输出 6

登录后复制

注意：当两数相差较大时，减法次数多，性能较差。可结合位运算优化成“更相减损术 + 移位”（如 Stein 算法），但在一般场景中不常用。

基本上就这些。日常使用推荐 math.gcd()，学习算法理解可用欧几里得，了解数学历史可以看看减损术。不复杂但容易忽略细节。

以上就是python中求最大公约数的三种方法的详细内容，更多请关注php中文网其它相关文章！