怎么使用python輾轉相除法求最大公約數和最小公倍數

本文小編為大家詳細介紹“怎么使用python輾轉相除法求最大公約數和最小公倍數”，內容詳細，步驟清晰，細節處理妥當，希望這篇“怎么使用python輾轉相除法求最大公約數和最小公倍數”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

輾轉相除法求最大公約數和最小公倍數

輾轉相除法數學原理

輾轉相除法也稱歐幾里得算法，是用來求兩個正整數的最大公約數的算法。接下來我們用實例來解釋一下。假如我們需要求12和21的最大公約數，用輾轉相除法是這樣實現的：

21 / 12 = 1 （余 9）
12 / 9 = 1（余 3）
9 / 3 = 3 （余 0）

至此，得到21與12的最大公約數為3（注意：這里的3是第二個式子取余得到的3，而非最后一個式子相除得到的），然后把兩個數相乘再除以最大公約數就可以得到最小公倍數：（21*12）/ 3 = 84

python代碼實現

接下來我們用python代碼來實現這樣一道題目：

題目：輸入兩個正整數，求其最大公約數和最小公倍數。

def func(m,n):
    a = m
    b = n
    # 默認m>n，若不是，則交換
    if m < n:
        m,n = n,m
    while n != 0:
        # 對m除n取余
        r = m % n
        m = n
        n = r
    return m,(a*b)/m

print("正整數m與n的最大公約數與最小公倍數分別為：",func(12,21))

正整數m與n的最大公約數與最小公倍數分別為： (3, 84.0)

用遞歸的方式實現

def rec(m,n):
    # 默認m>n，若不是，則交換
    if m < n:
        m,n = n,m
    # 終止條件    
    if n == 0:
        return m,(a*b)/m
    # 遞歸部分
    return rec(n,m%n)

a = 12
b = 21

print("正整數m與n的最大公約數與最小公倍數分別為：",rec(12,21))

正整數m與n的最大公約數與最小公倍數分別為： (3, 84.0)

Python3 20.輾轉相除法

算法分析

1.算法定義為：在有限的步驟內解決數學問題的程序，即為了解決某項工作或某個問題，所需要有限數量的機械性或重復性指令與計算步驟。

2.最大公約數：可整除兩個整數的最大整數。

3.用兩個數中較大的整數除以較小的數，求得商和余數。

源代碼

# coding:gbk
Num_1 = int(input("請輸入一個整數： "))
Num_2 = int(input("請輸入一個整數： "))

if Num_1 < Num_2:
	Tmp_Num = Num_1       # 是交換而不是賦值
	Num_1 = Num_2
	Num_2 = Tmp_Num

while Num_2 != 0:
	Tmp_Num = Num_1 % Num_2
	Num_1 = Num_2
	Num_2 = Tmp_Num

print('輸出這兩個整數的最大公約數：', Num_1)

結果截圖

讀到這里，這篇“怎么使用python輾轉相除法求最大公約數和最小公倍數”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。