最小公倍數(shù)的幾種解題方法

方法1

代碼思路

• 輸入?yún)?shù)：接收兩個整數(shù) m 和 n。
• 確定較大值：判斷 m 和 n 哪個更大，將較大的值存儲在變量 bigger 中。
• 尋找最小公倍數(shù)：
  • 使用一個 while 循環(huán)，從 bigger 開始不斷遞增。
  • 在每次循環(huán)中，檢查當(dāng)前 bigger 是否能同時被 m 和 n 整除。
  • 如果可以，則返回當(dāng)前的 bigger 作為最小公倍數(shù)。
  • 如果不可以，則將 bigger 增加 1，繼續(xù)下一次循環(huán)。
• 輸出結(jié)果：調(diào)用函數(shù)并打印最小公倍數(shù)

  def f1(m, n):  
      # 確定 m 和 n 中較大的值  
      if m > n:  
          bigger = m  
      else:  
          bigger = n  
        
      # 從較大的值開始，不斷遞增，尋找最小公倍數(shù)  
      while True:  
          # 檢查當(dāng)前的 bigger 是否能同時被 m 和 n 整除  
          if bigger % m == 0 and bigger % n == 0:  
              # 如果可以，返回當(dāng)前的 bigger 作為最小公倍數(shù)  
              return bigger  
          else:  
              # 如果不可以，將 bigger 增加 1，繼續(xù)循環(huán)  
              bigger += 1  
    
  # 調(diào)用函數(shù)并打印結(jié)果  
  # 示例：計算 23 和 74 的最小公倍數(shù)  
  print("%d 是最小公倍數(shù)" % f1(23, 74))

方法2

代碼思路

• 輸入?yún)?shù)：接收兩個整數(shù) m 和 n。
• 確定較大值：判斷 m 和 n 哪個更大，將較大的值存儲在變量 bigger 中。
• 尋找最小公倍數(shù)：
  • 初始化一個計數(shù)器 i 為1。
  • 使用一個 while 循環(huán)，不斷遞增 i。
  • 在每次循環(huán)中，計算 bigger * i，并檢查這個值是否能同時被 m 和 n 整除。
  • 如果可以，則返回 bigger * i 作為最小公倍數(shù)。
  • 如果不可以，則繼續(xù)下一次循環(huán)。
• 輸出結(jié)果：調(diào)用函數(shù)并打印最小公倍數(shù)。

def f2(m, n):  
    # 確定 m 和 n 中較大的值，作為起點可以減少一些不必要的乘法運算  
    if m > n:  
        bigger = m  
    else:  
        bigger = n  
      
    # 初始化計數(shù)器 i  
    i = 1  
      
    # 從1開始不斷遞增，尋找最小公倍數(shù)  
    while True:  
        # 計算當(dāng)前 bigger * i 的值  
        current_value = bigger * i  
          
        # 檢查當(dāng)前的 current_value 是否能同時被 m 和 n 整除  
        if current_value % m == 0 and current_value % n == 0:  
            # 如果可以，返回當(dāng)前的 current_value 作為最小公倍數(shù)  
            return current_value  
        else:  
            # 如果不可以，將計數(shù)器 i 增加 1，繼續(xù)循環(huán)  
            i += 1  
  
# 調(diào)用函數(shù)并打印結(jié)果  
# 示例：計算 23 和 74 的最小公倍數(shù)  
print("%d 是最小公倍數(shù)" % f2(23, 74))

方法3

代碼思路

• 導(dǎo)入math模塊：math模塊提供了許多數(shù)學(xué)函數(shù)，包括計算最大公約數(shù)（GCD）和最小公倍數(shù)（LCM）的函數(shù)。
• 使用math.lcm函數(shù)：直接調(diào)用math.lcm函數(shù)來計算兩個數(shù)的最小公倍數(shù)，并打印結(jié)果。
• 使用GCD計算LCM：根據(jù)最小公倍數(shù)和最大公約數(shù)的關(guān)系，LCM(a, b) = abs(a * b) // GCD(a, b)，來計算兩個數(shù)的最小公倍數(shù)，并打印結(jié)果。這里使用了整除運算符//來確保結(jié)果是整數(shù)。

import math  
  
# 使用math.lcm函數(shù)計算23和74的最小公倍數(shù)，并打印結(jié)果  
print("%d是最小公倍數(shù)" % math.lcm(23, 74))  
  
# 使用GCD計算LCM  
# 根據(jù)公式 LCM(a, b) = abs(a * b) // GCD(a, b)  
# 計算23和74的乘積的絕對值（雖然這里23和74都是正數(shù)，絕對值不是必需的，但為了一般性可以加上）  
# 然后除以它們的最大公約數(shù)，得到最小公倍數(shù)  
lcm_using_gcd = abs(23 * 74) // math.gcd(23, 74)  
# 打印結(jié)果  
print("%d是最小公倍數(shù)" % lcm_using_gcd)

最大公約數(shù)的幾種解題方法

方法1

代碼思路

• 輸入?yún)?shù)：接收兩個整數(shù)m和n。
• 確定較小值：判斷m和n哪個更小，將較小的值存儲在變量smaller中。
• 尋找最大公約數(shù)：
  • 從smaller遞減到1。
  • 在每次循環(huán)中，檢查當(dāng)前的數(shù)是否能同時被m和n整除。
  • 如果可以，則返回這個數(shù)作為最大公約數(shù)。
  • 如果不可以，則繼續(xù)下一次循環(huán)。
• 輸出結(jié)果：調(diào)用函數(shù)并打印最大公約數(shù)

def f1(m, n):  
    # 確定 m 和 n 中較小的值  
    if m < n:  
        smaller = m  
    else:  
        smaller = n  
      
    # 從 smaller 遞減到 1，尋找最大公約數(shù)  
    for i in range(smaller, 0, -1):  # 注意這里的步長是-1，表示遞減  
        # 檢查當(dāng)前的 i 是否能同時被 m 和 n 整除  
        if m % i == 0 and n % i == 0:  
            # 如果可以，返回 i 作為最大公約數(shù)  
            return i  
  
# 調(diào)用函數(shù)并打印結(jié)果  
# 示例：計算 12 和 36 的最大公約數(shù)  
print("%d是最大公約數(shù)" % f1(12, 36))

方法2

代碼思路

• 輸入?yún)?shù)：接收兩個整數(shù)m和n。
• 確定較小值：使用min函數(shù)找出m和n中的較小值，存儲在變量smaller中。
• 尋找公約數(shù)：
  • 初始化一個空列表f來存儲找到的公約數(shù)。
  • 使用for循環(huán)遍歷從1到smaller的所有整數(shù)。
  • 在每次循環(huán)中，檢查當(dāng)前的整數(shù)是否能同時被m和n整除。
  • 如果可以，將這個整數(shù)添加到列表f中。
• 返回最大公約數(shù)：使用max函數(shù)找出列表f中的最大值，并返回它。
• 輸出結(jié)果：調(diào)用函數(shù)并打印返回的最大公約數(shù)。

def f2(m, n):  
    # 確定 m 和 n 中的較小值  
    smaller = min(m, n)  
      
    # 初始化一個空列表來存儲公約數(shù)  
    f = []  
      
    # 遍歷從1到smaller的所有整數(shù)  
    for i in range(1, smaller + 1):  
        # 檢查當(dāng)前的整數(shù)是否能同時被 m 和 n 整除  
        if m % i == 0 and n % i == 0:  
            # 如果可以，將這個整數(shù)添加到列表 f 中  
            f.append(i)  
      
    # 返回列表 f 中的最大值，即最大公約數(shù)  
    return max(f)  
  
# 調(diào)用函數(shù)并打印返回的最大公約數(shù)  
# 示例：計算 12 和 36 的最大公約數(shù)  
print("%d是最大公約數(shù)" % f2(12, 36))

方法3（輾轉(zhuǎn)相除法）

代碼思路：

• 輸入檢查與調(diào)整：
  • 函數(shù)f1接收兩個整數(shù)m和n作為輸入。
  • 為了確保m不小于n，若m小于n，則兩者進行交換。
• 計算最大公約數(shù)：
  • 使用while循環(huán)，條件是n不為0。
  • 在循環(huán)內(nèi)部，利用元組解包同時更新m和n的值：m被賦值為當(dāng)前的n，而n被賦值為m % n（即m除以n的余數(shù)）。
  • 此過程會不斷迭代，直至n變?yōu)?。
• 返回結(jié)果：
  • 當(dāng)n為0時，m中存儲的即為所求的最大公約數(shù)，函數(shù)返回m。

def f3(m, n):  
    # 若m小于n，則交換m和n的值，確保m不小于n（此步驟可選）  
    if m < n:  
        m, n = n, m  # 利用元組解包進行值交換  
      
    # 當(dāng)n不為0時，持續(xù)進行循環(huán)計算  
    while n:  
        # 利用元組解包同時更新m和n的值  
        # m被更新為當(dāng)前的n，n被更新為m除以n的余數(shù)  
        m, n = n, m % n  
      
    # 當(dāng)n為0時，m即為所求的最大公約數(shù)  
    return m  
  
# 調(diào)用函數(shù)f3，并打印出12和24的最大公約數(shù)  
print(f3(12, 24))  # 輸出結(jié)果應(yīng)為12

方法4

在Python中，math模塊提供了一個名為gcd的函數(shù)，該函數(shù)能夠高效地計算出兩個或多個整數(shù)的最大公約數(shù)（GCD, Greatest Common Divisor）

import math  
  
# 調(diào)用math.gcd函數(shù)計算3139和2117的最大公約數(shù)  
result = math.gcd(3139, 2117)  
  
# 打印結(jié)果  
print(result)

總結(jié) 

到此這篇關(guān)于Python求最小公倍數(shù)與最大公約數(shù)的文章就介紹到這了,更多相關(guān)Python求最小公倍數(shù)與最大公約數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論