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
while r != 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

代碼：

def fuc2(p, q):
    while p!=q:
        if p>q:
            p = p - q
        else:
            q = q - p
    return p

方法三：枚舉法

代碼：

#枚舉法
def fun3(a,b):
    p = a*b
    t = a   #將a值賦給t
    while t>0 :
        if a%t==0 and b%t==0 : #若a除以t的余數和b除以t的余數都為0時，跳出循環
            break
        t=t-1                   #t>0時，每循環一次，t值減一
    print("枚舉法得最大公約數為：", t)         #當跳出循環時，輸出t值即為最大公約數
    
#用枚舉法求三個正整數的最大公約數
def fun4(a,b,c):
    p = a*b*c
    if a<b :
        min = a
    else :
        min = b
        if min>c :
            min = c                             #找出輸入的a,b,c三個數中的最小的數賦給min
    while min>0 :
        if a%min==0 and b%min==0 and c%min==0 :  #若a除以的余數和b除以min的余數和c除以min都為0時，跳出循環
            break
        min=min-1                               #>0時，每循環一次，min值減一
    print("枚舉法得三個數的最大公約數為：", min)  # 當跳出循環時，輸出min值即為最大公約數

以上是“python中求最大公約數的方法有哪些”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！