Python實現(xiàn)的求解最大公約數(shù)算法示例
本文實例講述了Python實現(xiàn)的求解最大公約數(shù)算法。分享給大家供大家參考，具體如下：
使用Python求解兩個數(shù)的最大公約數(shù)的時候用到了前面介紹的分解質(zhì)因式。其實，我寫分解質(zhì)因式程序的時候就是因為發(fā)現(xiàn)在實現(xiàn)最大公約數(shù)求解的過程中用到了這個功能。
比較令我開心的是之前學的一點Python集合處理功能居然在這個時候也派上了用場，小程序的完成讓人感覺比較舒心。
代碼實現(xiàn)如下：
#!/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))
程序的執(zhí)行結(jié)果如下：
E:\WorkSpace\01_編程語言\03_Python\math>python max_divisor.py
6
1
1
8
9
通過驗證，計算結(jié)果準確。
PS：這里再為大家推薦一款本站相關(guān)在線工具供大家參考：
在線最小公倍數(shù)/最大公約數(shù)計算工具：
http://tools.jb51.net/jisuanqi/gbs_gys_calc
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)學運算技巧總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對大家Python程序設計有所幫助。
相關(guān)文章
這篇文章主要介紹了Python多線程thread及模塊使用實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-04-04
如何對csv文件數(shù)據(jù)分組,并用pyecharts展示
這篇文章主要介紹了如何對csv文件數(shù)據(jù)分組,并用pyecharts展示，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
python創(chuàng)建列表和向列表添加元素的實現(xiàn)方法
下面小編就為大家分享一篇python創(chuàng)建列表和向列表添加元素的實現(xiàn)方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2017-12-12
字符畫是一系列字符的組合，我們可以把字符看作是比較大塊的像素，一個字符能表現(xiàn)一種顏色，字符的種類越多，可以表現(xiàn)的顏色也越多，圖片也會更有層次感。?本文將利用Python字符畫繪制一個甜心教主王心凌，需要的可以參考一下2022-05-05
這篇文章主要介紹了Python編程中裝飾器的使用示例解析,包括裝飾函數(shù)和方法,含參的裝飾器以及裝飾類這三個方面,需要的朋友可以參考下2016-06-06
Python使用pymssql連接SQL?SEVER數(shù)據(jù)庫全流程
SQL Server是微軟推出的重量級的數(shù)據(jù)庫,目前有多個版本,如2000、2008、2012等,下面這篇文章主要給大家介紹了關(guān)于Python使用pymssql連接SQL?SEVER數(shù)據(jù)庫的相關(guān)資料,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了Python自動化構(gòu)建工具scons使用入門筆記,本文講解了安裝scons、scons常用命令、scons使用示例等內(nèi)容,需要的朋友可以參考下2015-03-03
這篇文章主要為大家介紹了人工智能深度學習OpenAI?baselines的使用方法，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-05-05
這篇文章主要介紹了python獲取當前計算機cpu數(shù)量的方法,涉及Python操作計算機硬件的技巧,代碼簡單易懂,非常具有實用價值,需要的朋友可以參考下2015-04-04
今天小編就為大家分享一篇Python3 chardet模塊查看編碼格式的例子，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-08-08