小編寫這篇文章的主要目的，主要是給大家講解一下，關(guān)于最大公約數(shù)的求解方法，下面小編集中給大家總結(jié)一下，具體操作的五種方法。

　　方法一：短除法

　　短除法是求最大公因數(shù)的一種方法，也可用來求最小公倍數(shù)。求幾個(gè)數(shù)最大公因數(shù)的方法，開始時(shí)用觀察比較的方法，即：先把每個(gè)數(shù)的因數(shù)找出來，然后再找出公因數(shù)，最后在公因數(shù)中找出最大公因數(shù)。后來，使用分解質(zhì)因數(shù)法來分別分解兩個(gè)數(shù)的因數(shù)，再進(jìn)行運(yùn)算。之后又演變?yōu)槎坛?。短除法運(yùn)算方法是先用一個(gè)除數(shù)除以能被它除盡的一個(gè)質(zhì)數(shù)，以此類推，除到兩個(gè)數(shù)的商是互質(zhì)數(shù)為止。

　　簡單來說就是逐步找出兩個(gè)數(shù)的所有公約數(shù)，再將這些公約數(shù)累乘起來，就能得到最大公約數(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ù)累乘起來
　　a/=i
　　b/=i
　　print((f"{m},{n}的最大公約數(shù)為：{t}"))

　　這種方法雖然有點(diǎn)麻煩，但是邏輯卻很清楚，不容易出錯(cuò)。

　　方法二：歐幾里得算法（輾轉(zhuǎn)相除法）

　　歐幾里得算法是用來求兩個(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ù)的算法，它原本是為約分而設(shè)計(jì)的，但它適用于任何需要求最大公約數(shù)的場(chǎng)合。原文是：

　　可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之。

　　白話文譯文：

　　（如果需要對(duì)分?jǐn)?shù)進(jìn)行約分，那么）可以折半的話，就折半（也就是用2來約分）。如果不可以折半的話，那么就比較分母和分子的大小，用大數(shù)減去小數(shù)，互相減來減去，一直到減數(shù)與差相等為止，用這個(gè)相等的數(shù)字來約分。

　　具體步驟：

　　第一步：任意給定兩個(gè)正整數(shù)；判斷它們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。

　　第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止。

　　則第一步中約掉的若干個(gè)2的積與第二步中等數(shù)的乘積就是所求的最大公約數(shù)。

　　其中所說的“等數(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算法

　　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)算法，無論從理論還是從實(shí)際效率上都是很好的。但是卻有一個(gè)致命的缺陷，這個(gè)缺陷在素?cái)?shù)比較小的時(shí)候一般是感覺不到的，只有在大素?cái)?shù)時(shí)才會(huì)顯現(xiàn)出來。

　　一般實(shí)際應(yīng)用中的整數(shù)很少會(huì)超過64位(當(dāng)然已經(jīng)允許128位了)，對(duì)于這樣的整數(shù)，計(jì)算兩個(gè)數(shù)之間的模是很簡單的。對(duì)于字長為32位的平臺(tái)，計(jì)算兩個(gè)不超過32位的整數(shù)的模，只需要一個(gè)指令周期，而計(jì)算64位以下的整數(shù)模，也不過幾個(gè)周期而已。但是對(duì)于更大的素?cái)?shù)，這樣的計(jì)算過程就不得不由用戶來設(shè)計(jì)，為了計(jì)算兩個(gè)超過64位的整數(shù)的模，用戶也許不得不采用類似于多位數(shù)除法手算過程中的試商法，這個(gè)過程不但復(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í)，說明兩個(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í)，說明計(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}")

　　以上就是小編給大家總結(jié)的關(guān)于python實(shí)現(xiàn)最大公約數(shù)的五種具體方法，希望可以給大家?guī)韼椭?/p>