在計(jì)算機(jī)編程中，代碼中會(huì)顯示出很多的數(shù)學(xué)算法，數(shù)學(xué)算法可以通過(guò)最小的付出，完成最多的工作。如果我們想要做一件事情，會(huì)規(guī)劃好行動(dòng)步驟，而算法，就是你所編程序的執(zhí)行步驟。算法是計(jì)算機(jī)程序的靈魂，是程序的精髓所在，程序執(zhí)行效率的高低直接取決于算法的優(yōu)劣。下面，小編就交給大家?guī)追N在python中求取公約數(shù)的方法。

幾個(gè)整數(shù)同時(shí)均能整除的整數(shù).如果一個(gè)整數(shù)同時(shí)是幾個(gè)整數(shù)的約數(shù),稱(chēng)這個(gè)整數(shù)為它們的“公約數(shù)”;公約數(shù)中稱(chēng)為公約數(shù)

方法一：輾轉(zhuǎn)相除法

(1)比較兩數(shù)，并使m>n

(2)將m作被除數(shù)，n做除數(shù)，相除后余數(shù)為r

(3)循環(huán)判斷r，若r==0，則n為公約數(shù)，結(jié)束循環(huán)。若r!=0，執(zhí)行m=n，n=r;將m作被除數(shù)，n做除數(shù)，相除后余數(shù)為r

代碼：

num1=int(input("請(qǐng)輸入第一個(gè)數(shù)字："))

num2=int(input("請(qǐng)輸入第一個(gè)數(shù)字："))

m=max(num1,num2)

n=min(num1,num2)

r=m%n

whiler!=0:

m=n

n=r

r=m%n

print(num1,"和",num2,"的公約數(shù)為",n)

方法二：輾轉(zhuǎn)相減法

(1)如果p>q，p=p-q

(2)如果q>p，q=q-p

(3)假如p=q，則p或q是公約數(shù)

(4)如果p!=q,則繼續(xù)繼續(xù)相減，直至p=q

代碼：

deffuc2(p,q):

whilep!=q:

ifp>q:

p=p-q

else:

q=q-p

returnp

方法三：枚舉法

代碼：

#枚舉法

deffun3(a,b):

p=a*b

t=a#將a值賦給t

whilet>0:

ifa%t==0andb%t==0:#若a除以t的余數(shù)和b除以t的余數(shù)都為0時(shí)，跳出循環(huán)

break

t=t-1#t>0時(shí)，每循環(huán)一次，t值減一

print("枚舉法得公約數(shù)為：",t)#當(dāng)跳出循環(huán)時(shí)，輸出t值即為公約數(shù)

#用枚舉法求三個(gè)正整數(shù)的公約數(shù)

deffun4(a,b,c):

p=a*b*c

ifa

min=a

else:

min=b

ifmin>c:

min=c#找出輸入的a,b,c三個(gè)數(shù)中的最小的數(shù)賦給min

whilemin>0:

ifa%min==0andb%min==0andc%min==0:#若a除以的余數(shù)和b除以min的余數(shù)和c除以min都為0時(shí)，跳出循環(huán)

break

min=min-1#>0時(shí)，每循環(huán)一次，min值減一

print("枚舉法得三個(gè)數(shù)的公約數(shù)為：",min)#當(dāng)跳出循環(huán)時(shí)，輸出min值即為公約數(shù)

以上內(nèi)容為大家介紹了python中求最大公約數(shù)的三種方法，希望對(duì)大家有所幫助，如果想要了解更多Python相關(guān)知識(shí)，請(qǐng)關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。