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

2020-01-04 15:15:00

字体：大中小

来源：转载

供稿：网友

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

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

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

#!/usr/bin/pythonfrom collections import Counterdef 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_valuedef 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_multipleprint(LeastCommonMultiple(12,18))print(LeastCommonMultiple(7,2))print(LeastCommonMultiple(7,13))print(LeastCommonMultiple(24,56))print(LeastCommonMultiple(63,81))

程序执行结果：