开操网,99久久精品视香蕉蕉er热资源,亚洲三页

本文實例講述了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))