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程序设计有所帮助。

相关文章

OpenCV2从摄像头获取帧并写入视频文件的方法

一段基于OpenCV2的代码。 作用是从摄像头获取帧并将帧写入指定的视频文件中。 需要注意的是,视频文件所在的路径需要存在,例如D:/images/1.avi。images这个目录需要存...

python中的set实现不重复的排序原理

python中的set实现不重复的排序原理

最近在尝试写选课系统的时候遇到一个问题:   1、存在两个类 School、Teacher ;   2、School实例中包含多个Teacher的实例,但又不可重复   本人想到在Sch...

详解Python字符串切片

详解Python字符串切片

在python中,我们定义好一个字符串,如下所示。 在python中定义个字符串然后把它赋值给一个变量。 我们可以通过下标访问单个的字符,跟所有的语言一样,下标从0开始(==,我自己...

CentOS6.5设置Django开发环境

今天在我的Centos6.5机器上安装 Django 开发环境,在安装完使用 “django-admin.py startproject myapp” 创建应用的时候报了下面的错误...

Python中动态创建类实例的方法

简介 在Java中我们可以通过反射来根据类名创建类实例,那么在Python我们怎么实现类似功能呢? 其实在Python有一个builtin函数import,我们可以使用这个函数来在运行时...