Python实现的求解最小公倍数算法示例

yipeiwu_com5年前Python基础

本文实例讲述了Python实现的求解最小公倍数算法。分享给大家供大家参考,具体如下:

简单分析了一下,前面介绍的最大公约数的求解方法跟最小公倍数求解方法类似,只需要改一个简单的条件,然后做一点简单的其他计算。问题的解决也是基于分解质因式的程序。

程序实现以及测试case代码如下:

#!/usr/bin/python
from collections import Counter
def PrimeNum(num):
  r_value =[]
  for i in range(2,num+1):
   for j in range(2,i):
     if i % j == 0:
      break
   else:
     r_value.append(i)
  return r_value
def PrimeFactorSolve(num,prime_list):
  for n in prime_list:
   if num % n == 0:
     return [n,num / n]
def PrimeDivisor(num):
  num_temp =num
  prime_range= PrimeNum(num)
  ret_value =[]
  while num not in prime_range:
   factor_list= PrimeFactorSolve(num,prime_range)
   ret_value.append(factor_list[0])
   num =factor_list[1]
  else:
   ret_value.append(num)
  return Counter(ret_value)
def LeastCommonMultiple(num1,num2):
  dict1 =PrimeDivisor(num1)
  dict2 =PrimeDivisor(num2)
  least_common_multiple= 1
  for key in dict1:
   if key in dict2:
     if dict1[key] > dict2[key]:
      least_common_multiple*= (key ** dict1[key])
     else:
      least_common_multiple*= (key ** dict2[key])
  for key in dict1:
   if key not in dict2:
     least_common_multiple*= (key ** dict1[key])
  for key in dict2:
   if key not in dict1:
     least_common_multiple*= (key ** dict2[key])
  return least_common_multiple
print(LeastCommonMultiple(12,18))
print(LeastCommonMultiple(7,2))
print(LeastCommonMultiple(7,13))
print(LeastCommonMultiple(24,56))
print(LeastCommonMultiple(63,81))

程序执行结果:

E:\WorkSpace\01_编程语言\03_Python\math>pythonleast_common_multiple.py
36
14
91
168
567

通过验证,计算结果准确。

PS:这里再为大家推荐一款本站相关在线工具供大家参考:

在线最小公倍数/最大公约数计算工具:
http://tools.jb51.net/jisuanqi/gbs_gys_calc

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数学运算技巧总结》、《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总

希望本文所述对大家Python程序设计有所帮助。

相关文章

python cs架构实现简单文件传输

python cs架构实现简单文件传输

本文为大家分享了python cs架构实现简单文件的传输代码,供大家参考,具体内容如下 要实现简单文件的传输我们必须考虑这些问题: 1.什么是c/s架构? 顾名思义,就是客户端端/服务器...

Django中URL的参数传递的实现

在Django中有非常强大的URL模块,可以按照开发者的想法来制定清晰的URL,同时支持正则表达式。此外,在URL中还可以传递参数。 1. Django处理请求的方式 1)&n...

Python编写简单的HTML页面合并脚本

最近写一个BootStrap页面...因为功能需要所以决定一个页面解决所有问题,然后用jQuery来动态显示功能....然而这样做的话页面会相当庞大,一堆隐藏模态窗口和功能div都堆在一...

Python实现微信消息防撤回功能的实例代码

Python实现微信消息防撤回功能的实例代码

微信(WeChat)是腾讯公司于2011年1月21日推出的一款社交软件,8年时间微信做到日活10亿,日消息量450亿。在此期间微信也推出了不少的功能如:“摇一摇”、“漂流瓶”、“朋友圈”...

利用PyCharm操作Github(仓库新建、更新,代码回滚)

利用PyCharm操作Github(仓库新建、更新,代码回滚)

  Github是目前世界上最流行的代码存储和分享平台,而PyCharm是Python圈中最流行的IDE,它很好地支持了Git操作。本文将会介绍如何利用PyCha...