本文實例講述了Python實現的求解最大公約數算法。分享給大家供大家參考，具體如下：

使用Python求解兩個數的最大公約數的時候用到了前面介紹的分解質因式。其實，我寫分解質因式程序的時候就是因為發現在實現最大公約數求解的過程中用到了這個功能。

比較令我開心的是之前學的一點Python集合處理功能居然在這個時候也派上了用場，小程序的完成讓人感覺比較舒心。

代碼實現如下：

#!/usr/bin/pythonfrom collections import Counterdef PrimeNum(num):  r_value =[]  for i inrange(2,num+1):   for jin range(2,i):     if i % j == 0:      break   else:     r_value.append(i)  return r_valuedef PrimeFactorSolve(num,prime_list):  for n inprime_list:   if num % n == 0:     return [n,num / n]def PrimeDivisor(num):  num_temp =num  prime_range= PrimeNum(num)  ret_value =[]  while numnot in prime_range:   factor_list= PrimeFactorSolve(num,prime_range)   ret_value.append(factor_list[0])   num =factor_list[1]  else:   ret_value.append(num)  return Counter(ret_value)def MaxDivisor(num1,num2):  dict1 =PrimeDivisor(num1)  dict2 =PrimeDivisor(num2)  max_divisor= 1  for key1 indict1:   if key1 in dict2:     if dict1[key1] < dict2[key1]:      max_divisor*= (key1 ** dict1[key1])     else:      max_divisor*= (key1 ** dict2[key1])  return max_divisorprint(MaxDivisor(12,18))print(MaxDivisor(7,2))print(MaxDivisor(7,13))print(MaxDivisor(24,56))print(MaxDivisor(63,81))

程序的執行結果如下：

E:/WorkSpace/01_編程語言/03_Python/math>python max_divisor.py
6
1
1
8
9

通過驗證，計算結果準確。

PS：這里再為大家推薦一款本站相關在線工具供大家參考：

在線最小公倍數/最大公約數計算工具：
http://tools.jb51.net/jisuanqi/gbs_gys_calc

更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數學運算技巧總結》、《Python數據結構與算法教程》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》、《Python入門與進階經典教程》及《Python文件與目錄操作技巧匯總》

希望本文所述對大家Python程序設計有所幫助。