发帖
翼度科技»论坛 › 编程开发 › python › 查看内容

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

破碎故事之心

3

主题

3

帖子

9

积分

新手上路

Rank: 1

积分
9
显示全部楼层
最小公倍数的几种解题方法



方法1






代码思路


  • 输入参数：接收两个整数
    1. m
    复制代码
    和
    1. n
    复制代码
    。
  • 确定较大值：判断
    1. m
    复制代码
    和
    1. n
    复制代码
    哪个更大，将较大的值存储在变量
    1. bigger
    复制代码
    中。
  • 寻找最小公倍数：

    • 使用一个
      1. while
      复制代码
      循环，从
      1. bigger
      复制代码
      开始不断递增。
    • 在每次循环中，检查当前
      1. bigger
      复制代码
      是否能同时被
      1. m
      复制代码
      和
      1. n
      复制代码
      整除。
    • 如果可以，则返回当前的
      1. bigger
      复制代码
      作为最小公倍数。
    • 如果不可以，则将
      1. bigger
      复制代码
      增加 1，继续下一次循环。

  • 输出结果：调用函数并打印最小公倍数
    1. def f1(m, n):  
    2.     # 确定 m 和 n 中较大的值  
    3.     if m > n:  
    4.         bigger = m  
    5.     else:  
    6.         bigger = n  
    7.       
    8.     # 从较大的值开始，不断递增，寻找最小公倍数  
    9.     while True:  
    10.         # 检查当前的 bigger 是否能同时被 m 和 n 整除  
    11.         if bigger % m == 0 and bigger % n == 0:  
    12.             # 如果可以，返回当前的 bigger 作为最小公倍数  
    13.             return bigger  
    14.         else:  
    15.             # 如果不可以，将 bigger 增加 1，继续循环  
    16.             bigger += 1  
    17.   
    18. # 调用函数并打印结果  
    19. # 示例：计算 23 和 74 的最小公倍数  
    20. print("%d 是最小公倍数" % f1(23, 74))
    复制代码


方法2

代码思路


  • 输入参数：接收两个整数
    1. m
    复制代码
    和
    1. n
    复制代码
    。
  • 确定较大值：判断
    1. m
    复制代码
    和
    1. n
    复制代码
    哪个更大，将较大的值存储在变量
    1. bigger
    复制代码
    中。
  • 寻找最小公倍数：

    • 初始化一个计数器
      1. i
      复制代码
      为1。
    • 使用一个
      1. while
      复制代码
      循环，不断递增
      1. i
      复制代码
      。
    • 在每次循环中，计算
      1. bigger * i
      复制代码
      ，并检查这个值是否能同时被
      1. m
      复制代码
      和
      1. n
      复制代码
      整除。
    • 如果可以，则返回
      1. bigger * i
      复制代码
      作为最小公倍数。
    • 如果不可以，则继续下一次循环。

  • 输出结果：调用函数并打印最小公倍数。
  1. def f2(m, n):  
  2.     # 确定 m 和 n 中较大的值，作为起点可以减少一些不必要的乘法运算  
  3.     if m > n:  
  4.         bigger = m  
  5.     else:  
  6.         bigger = n  
  7.       
  8.     # 初始化计数器 i  
  9.     i = 1  
  10.       
  11.     # 从1开始不断递增，寻找最小公倍数  
  12.     while True:  
  13.         # 计算当前 bigger * i 的值  
  14.         current_value = bigger * i  
  15.          
  16.         # 检查当前的 current_value 是否能同时被 m 和 n 整除  
  17.         if current_value % m == 0 and current_value % n == 0:  
  18.             # 如果可以，返回当前的 current_value 作为最小公倍数  
  19.             return current_value  
  20.         else:  
  21.             # 如果不可以，将计数器 i 增加 1，继续循环  
  22.             i += 1  
  23.   
  24. # 调用函数并打印结果  
  25. # 示例：计算 23 和 74 的最小公倍数  
  26. print("%d 是最小公倍数" % f2(23, 74))
复制代码
方法3

代码思路


  • 导入math模块：
    1. math
    复制代码
    模块提供了许多数学函数，包括计算最大公约数（GCD）和最小公倍数（LCM）的函数。
  • 使用math.lcm函数：直接调用
    1. math.lcm
    复制代码
    函数来计算两个数的最小公倍数，并打印结果。
  • 使用GCD计算LCM：根据最小公倍数和最大公约数的关系，
    1. LCM(a, b) = abs(a * b) // GCD(a, b)
    复制代码
    ，来计算两个数的最小公倍数，并打印结果。这里使用了整除运算符
    1. //
    复制代码
    来确保结果是整数。
  1. import math  
  2.   
  3. # 使用math.lcm函数计算23和74的最小公倍数，并打印结果  
  4. print("%d是最小公倍数" % math.lcm(23, 74))  
  5.   
  6. # 使用GCD计算LCM  
  7. # 根据公式 LCM(a, b) = abs(a * b) // GCD(a, b)  
  8. # 计算23和74的乘积的绝对值（虽然这里23和74都是正数，绝对值不是必需的，但为了一般性可以加上）  
  9. # 然后除以它们的最大公约数，得到最小公倍数  
  10. lcm_using_gcd = abs(23 * 74) // math.gcd(23, 74)  
  11. # 打印结果  
  12. print("%d是最小公倍数" % lcm_using_gcd)
复制代码
最大公约数的几种解题方法

方法1

代码思路


  • 输入参数：接收两个整数
    1. m
    复制代码
    和
    1. n
    复制代码
    。
  • 确定较小值：判断
    1. m
    复制代码
    和
    1. n
    复制代码
    哪个更小，将较小的值存储在变量
    1. smaller
    复制代码
    中。
  • 寻找最大公约数：

    • 从
      1. smaller
      复制代码
      递减到1。
    • 在每次循环中，检查当前的数是否能同时被
      1. m
      复制代码
      和
      1. n
      复制代码
      整除。
    • 如果可以，则返回这个数作为最大公约数。
    • 如果不可以，则继续下一次循环。

  • 输出结果：调用函数并打印最大公约数
  1. def f1(m, n):  
  2.     # 确定 m 和 n 中较小的值  
  3.     if m < n:  
  4.         smaller = m  
  5.     else:  
  6.         smaller = n  
  7.       
  8.     # 从 smaller 递减到 1，寻找最大公约数  
  9.     for i in range(smaller, 0, -1):  # 注意这里的步长是-1，表示递减  
  10.         # 检查当前的 i 是否能同时被 m 和 n 整除  
  11.         if m % i == 0 and n % i == 0:  
  12.             # 如果可以，返回 i 作为最大公约数  
  13.             return i  
  14.   
  15. # 调用函数并打印结果  
  16. # 示例：计算 12 和 36 的最大公约数  
  17. print("%d是最大公约数" % f1(12, 36))
复制代码
方法2

代码思路


  • 输入参数：接收两个整数
    1. m
    复制代码
    和
    1. n
    复制代码
    。
  • 确定较小值：使用
    1. min
    复制代码
    函数找出
    1. m
    复制代码
    和
    1. n
    复制代码
    中的较小值，存储在变量
    1. smaller
    复制代码
    中。
  • 寻找公约数：

    • 初始化一个空列表
      1. f
      复制代码
      来存储找到的公约数。
    • 使用
      1. for
      复制代码
      循环遍历从1到
      1. smaller
      复制代码
      的所有整数。
    • 在每次循环中，检查当前的整数是否能同时被
      1. m
      复制代码
      和
      1. n
      复制代码
      整除。
    • 如果可以，将这个整数添加到列表
      1. f
      复制代码
      中。

  • 返回最大公约数：使用
    1. max
    复制代码
    函数找出列表
    1. f
    复制代码
    中的最大值，并返回它。
  • 输出结果：调用函数并打印返回的最大公约数。
  1. def f2(m, n):  
  2.     # 确定 m 和 n 中的较小值  
  3.     smaller = min(m, n)  
  4.       
  5.     # 初始化一个空列表来存储公约数  
  6.     f = []  
  7.       
  8.     # 遍历从1到smaller的所有整数  
  9.     for i in range(1, smaller + 1):  
  10.         # 检查当前的整数是否能同时被 m 和 n 整除  
  11.         if m % i == 0 and n % i == 0:  
  12.             # 如果可以，将这个整数添加到列表 f 中  
  13.             f.append(i)  
  14.       
  15.     # 返回列表 f 中的最大值，即最大公约数  
  16.     return max(f)  
  17.   
  18. # 调用函数并打印返回的最大公约数  
  19. # 示例：计算 12 和 36 的最大公约数  
  20. print("%d是最大公约数" % f2(12, 36))
复制代码
方法3（辗转相除法）

代码思路：

  • 输入检查与调整：

    • 函数
      1. f1
      复制代码
      接收两个整数
      1. m
      复制代码
      和
      1. n
      复制代码
      作为输入。
    • 为了确保
      1. m
      复制代码
      不小于
      1. n
      复制代码
      ，若
      1. m
      复制代码
      小于
      1. n
      复制代码
      ，则两者进行交换。

  • 计算最大公约数：

    • 使用
      1. while
      复制代码
      循环，条件是
      1. n
      复制代码
      不为0。
    • 在循环内部，利用元组解包同时更新
      1. m
      复制代码
      和
      1. n
      复制代码
      的值：
      1. m
      复制代码
      被赋值为当前的
      1. n
      复制代码
      ，而
      1. n
      复制代码
      被赋值为
      1. m % n
      复制代码
      （即
      1. m
      复制代码
      除以
      1. n
      复制代码
      的余数）。
    • 此过程会不断迭代，直至
      1. n
      复制代码
      变为0。

  • 返回结果：

    • 当
      1. n
      复制代码
      为0时，
      1. m
      复制代码
      中存储的即为所求的最大公约数，函数返回
      1. m
      复制代码
      。

  1. def f3(m, n):  
  2.     # 若m小于n，则交换m和n的值，确保m不小于n（此步骤可选）  
  3.     if m < n:  
  4.         m, n = n, m  # 利用元组解包进行值交换  
  5.       
  6.     # 当n不为0时，持续进行循环计算  
  7.     while n:  
  8.         # 利用元组解包同时更新m和n的值  
  9.         # m被更新为当前的n，n被更新为m除以n的余数  
  10.         m, n = n, m % n  
  11.       
  12.     # 当n为0时，m即为所求的最大公约数  
  13.     return m  
  14.   
  15. # 调用函数f3，并打印出12和24的最大公约数  
  16. print(f3(12, 24))  # 输出结果应为12
复制代码
方法4

在Python中，
  1. math
复制代码
模块提供了一个名为
  1. gcd
复制代码
的函数，该函数能够高效地计算出两个或多个整数的最大公约数（GCD, Greatest Common Divisor）
  1. import math  
  2.   
  3. # 调用math.gcd函数计算3139和2117的最大公约数  
  4. result = math.gcd(3139, 2117)  
  5.   
  6. # 打印结果  
  7. print(result)
复制代码
总结

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

来源:https://www.jb51.net/python/331197bzc.htm
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！

上一篇: 最小公倍数Python实现的方法例子

下一篇: Python OpenCV获取图片的基本参数信息

发表于 2024-11-25 08:02:58

举报 回复 使用道具

返回列表 发新帖

Archiver|手机版|小黑屋|翼度科技

Copyright © 2001-2020, Tencent Cloud.　Powered by Discuz! X3.4