您好,登錄后才能下訂單哦!
今天小編給大家分享一下Python怎么求解最大公約數(shù)的相關(guān)知識(shí)點(diǎn),內(nèi)容詳細(xì),邏輯清晰,相信大部分人都還太了解這方面的知識(shí),所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來(lái)了解一下吧。
短除法是求最大公因數(shù)的一種方法,也可用來(lái)求最小公倍數(shù)。求幾個(gè)數(shù)最大公因數(shù)的方法,開始時(shí)用觀察比較的方法,即:先把每個(gè)數(shù)的因數(shù)找出來(lái),然后再找出公因數(shù),最后在公因數(shù)中找出最大公因數(shù)。后來(lái),使用分解質(zhì)因數(shù)法來(lái)分別分解兩個(gè)數(shù)的因數(shù),再進(jìn)行運(yùn)算。之后又演變?yōu)槎坛?。短除法運(yùn)算方法是先用一個(gè)除數(shù)除以能被它除盡的一個(gè)質(zhì)數(shù),以此類推,除到兩個(gè)數(shù)的商是互質(zhì)數(shù)為止。
簡(jiǎn)單來(lái)說(shuō)就是逐步找出兩個(gè)數(shù)的所有公約數(shù),再將這些公約數(shù)累乘起來(lái),就能得到最大公約數(shù)啦!
a=int(input("please input the first number:")) b=int(input("please input the second number:")) m,n=a,b # 創(chuàng)建兩個(gè)變量存儲(chǔ)a和b t=1 # 創(chuàng)建t作為最大公約數(shù)的載體 for i in range(2,min(a,b)): while (a%i==0 and b%i==0): t*=i # 所有公約數(shù)累乘起來(lái) a/=i b/=i print((f"{m},{n}的最大公約數(shù)為:{t}"))
這種方法雖然有點(diǎn)麻煩,但是邏輯卻很清楚,不容易出錯(cuò)。
歐幾里得算法是用來(lái)求兩個(gè)正整數(shù)最大公約數(shù)的算法。古希臘數(shù)學(xué)家歐幾里得在其著作《The Elements》中最早描述了這種算法,所以被命名為歐幾里得算法。
假如需要求 1997 和 615 兩個(gè)正整數(shù)的最大公約數(shù),用歐幾里得算法,是這樣進(jìn)行的:
1997 / 615 = 3······152
615 / 152 = 4······7
152 / 7 = 21······5
7 / 5 = 1······2
5 / 2 = 2······1
2 / 1 = 2······0
至此,最大公約數(shù)為1
以除數(shù)和余數(shù)反復(fù)做除法運(yùn)算,當(dāng)余數(shù)為 0 時(shí),取當(dāng)前算式除數(shù)為最大公約數(shù),所以就得出了 1997 和 615 的最大公約數(shù) 1。
明白了這其中的邏輯,我們就可以著手開始寫程序啦!
a=int(input("please input the first number:")) b=int(input("please input the second number:")) # 首先要給兩數(shù)排序,保證大數(shù)除以小數(shù) m=max(a,b) n=min(a,b) t=m%n while t!=0: m,n=n,t # 仔細(xì)觀察不難發(fā)現(xiàn):每個(gè)除式的m、n是都是上一個(gè)式子的n和余數(shù) t=m%n # 更新余數(shù) print(f"{a}和的最大公約數(shù)為{n}")
當(dāng)然了,遞歸方法也能實(shí)現(xiàn)歐幾里得算法。
def GCD(a,b): # 比較大小,保證大數(shù)除以小數(shù) if a<b: a,b=b,a # 判斷是否能整除,若能整除,直接返回被除數(shù) if a%b==0: return b # 若不能整除,則返回函數(shù)GCD,參數(shù)做相應(yīng)變化 else: return GCD(b,a%b) a=int(input("please input the first number:")) b=int(input("please input the second number:")) gcd=GCD(a,b) print(f"{a}和的最大公約數(shù)為{gcd}")
更相減損術(shù)是出自《九章算術(shù)》的一種求最大公約數(shù)的算法,它原本是為約分而設(shè)計(jì)的,但它適用于任何需要求最大公約數(shù)的場(chǎng)合。原文是:
可半者半之,不可半者,副置分母、子之?dāng)?shù),以少減多,更相減損,求其等也。以等數(shù)約之。
白話文譯文:
(如果需要對(duì)分?jǐn)?shù)進(jìn)行約分,那么)可以折半的話,就折半(也就是用2來(lái)約分)。如果不可以折半的話,那么就比較分母和分子的大小,用大數(shù)減去小數(shù),互相減來(lái)減去,一直到減數(shù)與差相等為止,用這個(gè)相等的數(shù)字來(lái)約分。
具體步驟:
第一步:任意給定兩個(gè)正整數(shù);判斷它們是否都是偶數(shù)。若是,則用2約簡(jiǎn);若不是則執(zhí)行第二步。
第二步:以較大的數(shù)減較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作,直到所得的減數(shù)和差相等為止。
則第一步中約掉的若干個(gè)2的積與第二步中等數(shù)的乘積就是所求的最大公約數(shù)。
其中所說(shuō)的“等數(shù)”,就是公約數(shù)。求“等數(shù)”的辦法是“更相減損”法。
現(xiàn)在使用更相減損術(shù)求98與63的最大公約數(shù)。
解:由于63不是偶數(shù),把98和63以大數(shù)減小數(shù),并輾轉(zhuǎn)相減:
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以,98和63的最大公約數(shù)等于7。
a=int(input("please input the first number:")) b=int(input("please input the second number:")) # 首先要給兩數(shù)排序,保證大數(shù)減小數(shù) m=max(a,b) n=min(a,b) # 判斷兩數(shù)是否都是偶數(shù),如果都是偶數(shù)就同時(shí)除2 while m%2==0 and n%2==0: m,n=m/2,n/2 t=m-n # 判斷條件是減數(shù)和差相等 while n!=t: m,n=max(n,t),min(n,t) # 每減一輪之后,都要重新判斷減數(shù)和差的大小,再次以大數(shù)減去小數(shù) t=m-n print(f"{a}和的最大公約數(shù)為{n}")
從兩個(gè)數(shù)中較小數(shù)開始,由小到大列舉,找出公約數(shù)并保證該公約數(shù)也屬于較大數(shù),這些公約數(shù)的最大者就是最大公約數(shù);也可以從大到小列舉,直到找出公約數(shù)后跳出循環(huán),該公約數(shù)即是最大公約數(shù)。
a=int(input("please input the first number:")) b=int(input("please input the second number:")) p,q=min(a,b),max(a,b) lst=[] for i in range(1,p+1): if p%i==0 and q%i==0: lst.append(i) gcd=max(lst) print(f"{a}和的最大公約數(shù)為{gcd}") #a=int(input("please input the first number:")) #b=int(input("please input the second number:")) #p,q=min(a,b),max(a,b) #gcd=0 #for i in range(p,0,-1): # if p%i==0 and q%i==0: # gcd=i # break #print(f"{a}和的最大公約數(shù)為{gcd}")
Stein算法是一種計(jì)算兩個(gè)數(shù)最大公約數(shù)的算法,是針對(duì)歐幾里德算法在對(duì)大整數(shù)進(jìn)行運(yùn)算時(shí),需要試商導(dǎo)致增加運(yùn)算時(shí)間的缺陷而提出的改進(jìn)算法。
歐幾里得算法缺陷:
歐幾里德算法是計(jì)算兩個(gè)數(shù)最大公約數(shù)的傳統(tǒng)算法,無(wú)論從理論還是從實(shí)際效率上都是很好的。但是卻有一個(gè)致命的缺陷,這個(gè)缺陷在素?cái)?shù)比較小的時(shí)候一般是感覺(jué)不到的,只有在大素?cái)?shù)時(shí)才會(huì)顯現(xiàn)出來(lái)。
一般實(shí)際應(yīng)用中的整數(shù)很少會(huì)超過(guò)64位(當(dāng)然已經(jīng)允許128位了),對(duì)于這樣的整數(shù),計(jì)算兩個(gè)數(shù)之間的模是很簡(jiǎn)單的。對(duì)于字長(zhǎng)為32位的平臺(tái),計(jì)算兩個(gè)不超過(guò)32位的整數(shù)的模,只需要一個(gè)指令周期,而計(jì)算64位以下的整數(shù)模,也不過(guò)幾個(gè)周期而已。但是對(duì)于更大的素?cái)?shù),這樣的計(jì)算過(guò)程就不得不由用戶來(lái)設(shè)計(jì),為了計(jì)算兩個(gè)超過(guò)64位的整數(shù)的模,用戶也許不得不采用類似于多位數(shù)除法手算過(guò)程中的試商法,這個(gè)過(guò)程不但復(fù)雜,而且消耗了很多CPU時(shí)間。對(duì)于現(xiàn)代密碼算法,要求計(jì)算128位以上的素?cái)?shù)的情況比比皆是,設(shè)計(jì)這樣的程序迫切希望能夠拋棄除法和取模。
看下面兩個(gè)結(jié)論:
gcd(a,a)=a,也就是一個(gè)數(shù)和其自身的公約數(shù)仍是其自身。
gcd(ka,kb)=k gcd(a,b),也就是最大公約數(shù)運(yùn)算和倍乘運(yùn)算可以交換。特殊地,當(dāng)k=2時(shí),說(shuō)明兩個(gè)偶數(shù)的最大公約數(shù)必然能被2整除。
當(dāng)k與b互為質(zhì)數(shù),gcd(ka,b)=gcd(a,b),也就是約掉兩個(gè)數(shù)中只有其中一個(gè)含有的因子不影響最大公約數(shù)。特殊地,當(dāng)k=2時(shí),說(shuō)明計(jì)算一個(gè)偶數(shù) 和一個(gè)奇數(shù)的最大公約數(shù)時(shí),可以先將偶數(shù)除以2。
:param a: 第一個(gè)數(shù)
:param b: 第二個(gè)數(shù)
:return: 最大公約數(shù)
def gcd_Stein(a, b): # 保證b比a小 if a < b: a, b = b, a if (0 == b): return a # a、b都是偶數(shù),除2右移一位即可 if a % 2 == 0 and b % 2 == 0: return 2 * gcd_Stein(a / 2, b / 2) # a是偶數(shù) if a % 2 == 0: return gcd_Stein(a / 2, b) # b是偶數(shù) if b % 2 == 0: return gcd_Stein(a, b / 2) # 都是奇數(shù) return gcd_Stein((a + b) / 2, (a - b) / 2) a=int(input("please input the first number:")) b=int(input("please input the second number:")) gcd=int(gcd_Stein(a,b)) print(f"{a}和的最大公約數(shù)為{gcd}")
以上就是“Python怎么求解最大公約數(shù)”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會(huì)為大家更新不同的知識(shí),如果還想學(xué)習(xí)更多的知識(shí),請(qǐng)關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。