正文

python如何取最大公因数

小六 /19 浏览量
0518

在Python中，求两个数的最大公因数（GCD）可以通过多种方法实现，以下是几种常见的方法：

欧几里得算法（辗转相除法）

 def gcd_euclidean（a, b）: while b: a, b = b, a % b return a

暴力枚举法

 def gcd_exhaustive（a, b）: for i in range（1, min（a, b） + 1）: if a % i == 0 and b % i == 0: return i

更相减损法

 def gcd_subtraction（a, b）: while a != b: if a > b: a = a - b else: b = b - a return a

使用内置`math`库的`gcd`函数

 import math  def gcd_math_lib（a, b）: return math.gcd（a, b）

短除法

 def gcd_short_division（a, b）: t = 1 while a % b == 0 and b != 0: t *= b a //= b b = a % b return t

以上方法中，欧几里得算法是最常用且效率较高的方法，其时间复杂度大约为O（log（max（a，b）））。

您可以根据需要选择合适的方法来计算最大公因数。

-- 展开阅读全文 --