python中求最大公約數的三種方法

在計算機編程中，代碼中會顯示出很多的數學算法，數學算法可以通過最小的付出，完成最多的工作。如果我們想要做一件事情，會規劃好行動步驟，而算法，就是你所編程序的執行步驟。算法是計算機程序的靈魂，是程序的精髓所在，程序執行效率的高低直接取決于算法的優劣。下面，小編就交給大家幾種在python中求取公約數的方法。

幾個整數同時均能整除的整數.如果一個整數同時是幾個整數的約數,稱這個整數為它們的“公約數”;公約數中稱為公約數

方法一：輾轉相除法

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

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

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

代碼：

num1=int(input("請輸入第一個數字："))

num2=int(input("請輸入第一個數字："))

m=max(num1,num2)

n=min(num1,num2)

r=m%n

whiler!=0:

m=n

n=r

r=m%n

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

方法二：輾轉相減法

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

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

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

(4)如果p!=q,則繼續繼續相減，直至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的余數和b除以t的余數都為0時，跳出循環

break

t=t-1#t>0時，每循環一次，t值減一

print("枚舉法得公約數為：",t)#當跳出循環時，輸出t值即為公約數

#用枚舉法求三個正整數的公約數

deffun4(a,b,c):

p=a*b*c

ifa

min=a

else:

min=b

ifmin>c:

min=c#找出輸入的a,b,c三個數中的最小的數賦給min

whilemin>0:

ifa%min==0andb%min==0andc%min==0:#若a除以的余數和b除以min的余數和c除以min都為0時，跳出循環

break

min=min-1#>0時，每循環一次，min值減一

print("枚舉法得三個數的公約數為：",min)#當跳出循環時，輸出min值即為公約數

以上內容為大家介紹了python中求最大公約數的三種方法，希望對大家有所幫助，如果想要了解更多Python相關知識，請關注IT培訓機構:千鋒教育。