Python에서 구현된 최소 공배수 알고리즘의 예-파이썬 튜토리얼-php.cn

Python에서 구현된 최소 공배수 알고리즘의 예

不言

풀어 주다： 2018-05-03 15:37:10

원래의

5353명이 탐색했습니다.

이 글에서는 주로 Python에서 구현한 최소 공배수를 해결하는 알고리즘을 소개합니다. Python 수치 연산, 판단 및 기타 관련 연산 기술이 필요한 친구가 참고할 수 있습니다.

이 글에서는 구현된 최소 공배수를 해결하는 알고리즘을 설명합니다. 파이썬에서. 참고하실 수 있도록 자세한 내용은 다음과 같습니다.

간단히 분석해 보면 앞서 소개한 최대공약수를 푸는 방법은 최소공배수를 푸는 방법과 비슷하다는 것을 알 수 있습니다. 간단한 조건을 적용한 다음 다른 간단한 계산을 수행합니다. 문제의 해결 역시 소인수분해 과정을 기반으로 합니다.

프로그램 구현 및 테스트 케이스 코드는 다음과 같습니다.

#!/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))

로그인 후 복사

프로그램 실행 결과: