最大公约数怎么求算法python

在Python中，求两个数的最大公约数（GCD）可以使用多种算法，以下是几种常见的算法及其Python实现：

穷举法

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

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

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

更相减损法

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

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

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

短除法

 def gcd_short_division（a, b）: m, n = a, b t = 1 while m != n: if m > n: m -= n else: n -= m t *= m return t 

质因数分解法

 from collections import Counter def PrimeNum（num）: r_value = [] for i in range（2, num + 1）: for j in range（2, i）: if i % j == 0: break else: r_value.append（i） return r_value def PrimeFactorSolve（num, prime_list）: for n in prime_list: if num % n == 0: return [n, num // n] return [num, 1] def PrimeDivisor（num）: num_temp = num prime_range = PrimeNum（num） ret_value = [] while num not in prime_range: factor_list = PrimeFactorSolve（num, prime_range） ret_value.append（factor_list） num = factor_list else: ret_value.append（num） return Counter（ret_value） def MaxDivisor（num1, num2）: dict1 = PrimeDivisor（num1） dict2 = PrimeDivisor（num2） max_divisor = 1 for key in dict1: if key in dict2: max_divisor = max（max_divisor, dict1[key] * dict2[key]） return max_divisor 

以上代码展示了使用不同方法计算最大公约数的Python实现。你可以根据具体需求选择合适的方法。需要注意的是，使用内置的`math.gcd`函数通常是最高效的选择