Python實現(xiàn)的求解最大公約數(shù)算法示例
本文實例講述了Python實現(xiàn)的求解最大公約數(shù)算法。分享給大家供大家參考，具體如下：
使用Python求解兩個數(shù)的最大公約數(shù)的時候用到了前面介紹的分解質(zhì)因式。其實，我寫分解質(zhì)因式程序的時候就是因為發(fā)現(xiàn)在實現(xiàn)最大公約數(shù)求解的過程中用到了這個功能。
比較令我開心的是之前學(xué)的一點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é)果準(zhǔn)確。
PS：這里再為大家推薦一款本站相關(guān)在線工具供大家參考：
在線最小公倍數(shù)/最大公約數(shù)計算工具：
http://tools.jb51.net/jisuanqi/gbs_gys_calc
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)學(xué)運(yùn)算技巧總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對大家Python程序設(shè)計有所幫助。
相關(guān)文章
近日在使用flask框架獲取前端的請求時獲取參數(shù)時，遇到了幾個問題,所以下面這篇文章主要給大家介紹了關(guān)于使用flask如何獲取post請求參數(shù)的相關(guān)資料,需要的朋友可以參考下2022-08-08
Python實現(xiàn)隨機(jī)生成有效手機(jī)號碼及身份證功能示例
這篇文章主要介紹了Python實現(xiàn)隨機(jī)生成有效手機(jī)號碼及身份證功能,結(jié)合完整實例形式分析了Python基于手機(jī)號與身份證算法實現(xiàn)隨機(jī)手機(jī)號及身份證的生成功能,涉及Python日期、隨機(jī)數(shù)、文件讀取等相關(guān)操作技巧,需要的朋友可以參考下2017-06-06
python2.7讀取文件夾下所有文件名稱及內(nèi)容的方法
python，本身來說是一門高級編程語言,python它入門簡單，有基礎(chǔ)的學(xué)起來很快就能有簡單的應(yīng)用，但是在非常高的抽象計算中，高級的python程序設(shè)計也是非常難學(xué)的。接下來給大家介紹python2.7讀取文件夾下所有文件名稱及內(nèi)容的方法，一起看看吧2018-02-02
這篇文章主要介紹了python二分查找算法的遞歸實現(xiàn)方法,結(jié)合實例形式分析了Python二分查找算法的相關(guān)實現(xiàn)技巧,需要的朋友可以參考下2016-05-05
Python中的協(xié)程(Coroutine)操作模塊(greenlet、gevent)
這篇文章介紹了Python中的協(xié)程(Coroutine)操作模塊(greenlet、gevent)，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-05-05
python基于socketserver實現(xiàn)并發(fā),驗證客戶端的合法性
TCP協(xié)議的socket一次只能和一個客戶端通信, 而socketsever可以時間和多個客戶端通信。本文將講解socketserver的具體使用2021-05-05
python+pyhyper實現(xiàn)識別圖片中的車牌號思路詳解
最近領(lǐng)導(dǎo)給布置了一個基于圖片識別車牌號的工具開發(fā)任務(wù)，然后就去研究實現(xiàn)邏輯，自己根據(jù)opencv寫了一個小demo，發(fā)現(xiàn)不僅速度慢而且成功率極低。然后，就找到了Hyperlpr開源項目，這篇文章主要介紹了python+pyhyper實現(xiàn)識別圖片中的車牌號,需要的朋友可以參考下2022-12-12
詳解python 3.6 安裝json 模塊(simplejson)
這篇文章主要介紹了python 3.6 安裝json 模塊(simplejson)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
這篇文章主要介紹了Python閉包的使用方法，當(dāng)返回的內(nèi)部函數(shù)使用了外部函數(shù)的變量就形成了閉包，下文更多相關(guān)內(nèi)容需要的小伙伴可以參考一下2022-04-04
一幅圖像由不同灰度值的像素組成，圖像中灰度的分布情況是該圖像的一個重要特征。圖像的灰度直方圖就描述了圖像中灰度分布情況。本文將利用Python和OpenCV繪制灰度直方圖，需要的可以參考一下2022-03-03