Python实现的求解最大公约数算法示例_Python

Python实现的求解最大公约数算法示例

2021-02-15 00:17grey_csdn Python

这篇文章主要介绍了Python实现的求解最大公约数算法,涉及Python数学运算相关操作技巧,需要的朋友可以参考下

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

使用Python求解两个数的最大公约数的时候用到了前面介绍的分解质因式。其实，我写分解质因式程序的时候就是因为发现在实现最大公约数求解的过程中用到了这个功能。

比较令我开心的是之前学的一点Python集合处理功能居然在这个时候也派上了用场，小程序的完成让人感觉比较舒心。

代码实现如下：

									#!/usr/bin/python

									from collections import Counter

									def PrimeNum(num):

									  r_value =[]

									  for i inrange(2,num+1):

									   for jin range(2,i):

									     if i % j == 0:

									      break

									   else:

									     r_value.append(i)

									  return r_value

									def PrimeFactorSolve(num,prime_list):

									  for n inprime_list:

									   if num % n == 0:

									     return [n,num / n]

									def PrimeDivisor(num):

									  num_temp =num

									  prime_range= PrimeNum(num)

									  ret_value =[]

									  while numnot 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 MaxDivisor(num1,num2):

									  dict1 =PrimeDivisor(num1)

									  dict2 =PrimeDivisor(num2)

									  max_divisor= 1

									  for key1 indict1:

									   if key1 in dict2:

									     if dict1[key1] < dict2[key1]:

									      max_divisor*= (key1 ** dict1[key1])

									     else:

									      max_divisor*= (key1 ** dict2[key1])

									  return max_divisor

									print(MaxDivisor(12,18))

									print(MaxDivisor(7,2))

									print(MaxDivisor(7,13))

									print(MaxDivisor(24,56))

									print(MaxDivisor(63,81))