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))

程序執行結果：