Python求最小公倍数与最大公约数代码示例与解题思路

最小公倍数的几种解题方法

方法1

代码思路

• 输入参数：接收两个整数 m 和 n。
• 确定较大值：判断 m 和 n 哪个更大，将较大的值存储在变量 bigger 中。
• 寻找最小公倍数：
  • 使用一个 while 循环，从 bigger 开始不断递增。
  • 在每次循环中，检查当前 bigger 是否能同时被 m 和 n 整除。
  • 如果可以，则返回当前的 bigger 作为最小公倍数。
  • 如果不可以，则将 bigger 增加 1，继续下一次循环。
• 输出结果：调用函数并打印最小公倍数

  def f1(m, n):  
      # 确定 m 和 n 中较大的值  
      if m > n:  
          bigger = m  
      else:  
          bigger = n  
        
      # 从较大的值开始，不断递增，寻找最小公倍数  
      while True:  
          # 检查当前的 bigger 是否能同时被 m 和 n 整除  
          if bigger % m == 0 and bigger % n == 0:  
              # 如果可以，返回当前的 bigger 作为最小公倍数  
              return bigger  
          else:  
              # 如果不可以，将 bigger 增加 1，继续循环  
              bigger += 1  
    
  # 调用函数并打印结果  
  # 示例：计算 23 和 74 的最小公倍数  
  print("%d 是最小公倍数" % f1(23, 74))

方法2

代码思路

• 输入参数：接收两个整数 m 和 n。
• 确定较大值：判断 m 和 n 哪个更大，将较大的值存储在变量 bigger 中。
• 寻找最小公倍数：
  • 初始化一个计数器 i 为1。
  • 使用一个 while 循环，不断递增 i。
  • 在每次循环中，计算 bigger * i，并检查这个值是否能同时被 m 和 n 整除。
  • 如果可以，则返回 bigger * i 作为最小公倍数。
  • 如果不可以，则继续下一次循环。
• 输出结果：调用函数并打印最小公倍数。

def f2(m, n):  
    # 确定 m 和 n 中较大的值，作为起点可以减少一些不必要的乘法运算  
    if m > n:  
        bigger = m  
    else:  
        bigger = n  
      
    # 初始化计数器 i  
    i = 1  
      
    # 从1开始不断递增，寻找最小公倍数  
    while True:  
        # 计算当前 bigger * i 的值  
        current_value = bigger * i  
          
        # 检查当前的 current_value 是否能同时被 m 和 n 整除  
        if current_value % m == 0 and current_value % n == 0:  
            # 如果可以，返回当前的 current_value 作为最小公倍数  
            return current_value  
        else:  
            # 如果不可以，将计数器 i 增加 1，继续循环  
            i += 1  
  
# 调用函数并打印结果  
# 示例：计算 23 和 74 的最小公倍数  
print("%d 是最小公倍数" % f2(23, 74))

方法3

代码思路

• 导入math模块：math模块提供了许多数学函数，包括计算最大公约数（GCD）和最小公倍数（LCM）的函数。
• 使用math.lcm函数：直接调用math.lcm函数来计算两个数的最小公倍数，并打印结果。
• 使用GCD计算LCM：根据最小公倍数和最大公约数的关系，LCM(a, b) = abs(a * b) // GCD(a, b)，来计算两个数的最小公倍数，并打印结果。这里使用了整除运算符//来确保结果是整数。

import math  
  
# 使用math.lcm函数计算23和74的最小公倍数，并打印结果  
print("%d是最小公倍数" % math.lcm(23, 74))  
  
# 使用GCD计算LCM  
# 根据公式 LCM(a, b) = abs(a * b) // GCD(a, b)  
# 计算23和74的乘积的绝对值（虽然这里23和74都是正数，绝对值不是必需的，但为了一般性可以加上）  
# 然后除以它们的最大公约数，得到最小公倍数  
lcm_using_gcd = abs(23 * 74) // math.gcd(23, 74)  
# 打印结果  
print("%d是最小公倍数" % lcm_using_gcd)

最大公约数的几种解题方法

方法1

代码思路

• 输入参数：接收两个整数m和n。
• 确定较小值：判断m和n哪个更小，将较小的值存储在变量smaller中。
• 寻找最大公约数：
  • 从smaller递减到1。
  • 在每次循环中，检查当前的数是否能同时被m和n整除。
  • 如果可以，则返回这个数作为最大公约数。
  • 如果不可以，则继续下一次循环。
• 输出结果：调用函数并打印最大公约数

def f1(m, n):  
    # 确定 m 和 n 中较小的值  
    if m < n:  
        smaller = m  
    else:  
        smaller = n  
      
    # 从 smaller 递减到 1，寻找最大公约数  
    for i in range(smaller, 0, -1):  # 注意这里的步长是-1，表示递减  
        # 检查当前的 i 是否能同时被 m 和 n 整除  
        if m % i == 0 and n % i == 0:  
            # 如果可以，返回 i 作为最大公约数  
            return i  
  
# 调用函数并打印结果  
# 示例：计算 12 和 36 的最大公约数  
print("%d是最大公约数" % f1(12, 36))

方法2

代码思路

• 输入参数：接收两个整数m和n。
• 确定较小值：使用min函数找出m和n中的较小值，存储在变量smaller中。
• 寻找公约数：
  • 初始化一个空列表f来存储找到的公约数。
  • 使用for循环遍历从1到smaller的所有整数。
  • 在每次循环中，检查当前的整数是否能同时被m和n整除。
  • 如果可以，将这个整数添加到列表f中。
• 返回最大公约数：使用max函数找出列表f中的最大值，并返回它。
• 输出结果：调用函数并打印返回的最大公约数。

def f2(m, n):  
    # 确定 m 和 n 中的较小值  
    smaller = min(m, n)  
      
    # 初始化一个空列表来存储公约数  
    f = []  
      
    # 遍历从1到smaller的所有整数  
    for i in range(1, smaller + 1):  
        # 检查当前的整数是否能同时被 m 和 n 整除  
        if m % i == 0 and n % i == 0:  
            # 如果可以，将这个整数添加到列表 f 中  
            f.append(i)  
      
    # 返回列表 f 中的最大值，即最大公约数  
    return max(f)  
  
# 调用函数并打印返回的最大公约数  
# 示例：计算 12 和 36 的最大公约数  
print("%d是最大公约数" % f2(12, 36))

方法3（辗转相除法）

代码思路：

• 输入检查与调整：
  • 函数f1接收两个整数m和n作为输入。
  • 为了确保m不小于n，若m小于n，则两者进行交换。
• 计算最大公约数：
  • 使用while循环，条件是n不为0。
  • 在循环内部，利用元组解包同时更新m和n的值：m被赋值为当前的n，而n被赋值为m % n（即m除以n的余数）。
  • 此过程会不断迭代，直至n变为0。
• 返回结果：
  • 当n为0时，m中存储的即为所求的最大公约数，函数返回m。

def f3(m, n):  
    # 若m小于n，则交换m和n的值，确保m不小于n（此步骤可选）  
    if m < n:  
        m, n = n, m  # 利用元组解包进行值交换  
      
    # 当n不为0时，持续进行循环计算  
    while n:  
        # 利用元组解包同时更新m和n的值  
        # m被更新为当前的n，n被更新为m除以n的余数  
        m, n = n, m % n  
      
    # 当n为0时，m即为所求的最大公约数  
    return m  
  
# 调用函数f3，并打印出12和24的最大公约数  
print(f3(12, 24))  # 输出结果应为12

方法4

在Python中，math模块提供了一个名为gcd的函数，该函数能够高效地计算出两个或多个整数的最大公约数（GCD, Greatest Common Divisor）

import math  
  
# 调用math.gcd函数计算3139和2117的最大公约数  
result = math.gcd(3139, 2117)  
  
# 打印结果  
print(result)

总结 

到此这篇关于Python求最小公倍数与最大公约数的文章就介绍到这了,更多相关Python求最小公倍数与最大公约数内容请搜索恩蓝小号以前的文章或继续浏览下面的相关文章希望大家以后多多支持恩蓝小号！