Home >Backend Development >Python Tutorial >Example of the least common multiple algorithm implemented in Python

Example of the least common multiple algorithm implemented in Python

不言
不言Original
2018-05-03 15:37:105361browse

This article mainly introduces the algorithm for solving the least common multiple implemented in Python, involving Python numerical operations, judgment and other related operating skills. Friends in need can refer to it

The example of this article describes the algorithm for solving the least common multiple implemented in Python algorithm. Share it with everyone for your reference, the details are as follows:

After a brief analysis, the method of solving the greatest common divisor introduced earlier is similar to the method of solving the least common multiple. You only need to change a simple condition, and then do something simple Other calculations. The solution of the problem is also based on the procedure of factoring prime factors.

The program implementation and test case code are as follows:

#!/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 Primepisor(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 =Primepisor(num1)
   dict2 =Primepisor(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))

Program execution result:

E:\WorkSpace \01_Programming Language\03_Python\math>pythonleast_common_multiple.py
36
14
91
168
567

Passed verification and the calculation result is accurate.

Related recommendations:

Example of prime factorization algorithm implemented in Python

##Example of algorithm for solving the greatest common divisor implemented in Python


The above is the detailed content of Example of the least common multiple algorithm implemented in Python. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn