如何使用Python實現求解最大公約數算法

這篇文章主要介紹了如何使用Python實現求解最大公約數算法，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

具體如下：

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

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

代碼實現如下：

#!/usr/bin/python
from collections import Counter
def 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_value
def 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_divisor
print(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

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

感謝你能夠認真閱讀完這篇文章，希望小編分享的“如何使用Python實現求解最大公約數算法”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!