Python實(shí)現(xiàn)的求解最大公約數(shù)算法示例

2020-01-04 15:15:05

字體：大中小

供稿：網(wǎng)友

本文實(shí)例講述了Python實(shí)現(xiàn)的求解最大公約數(shù)算法。分享給大家供大家參考，具體如下：

使用Python求解兩個(gè)數(shù)的最大公約數(shù)的時(shí)候用到了前面介紹的分解質(zhì)因式。其實(shí)，我寫分解質(zhì)因式程序的時(shí)候就是因?yàn)榘l(fā)現(xiàn)在實(shí)現(xiàn)最大公約數(shù)求解的過程中用到了這個(gè)功能。

比較令我開心的是之前學(xué)的一點(diǎn)Python集合處理功能居然在這個(gè)時(shí)候也派上了用場(chǎng)，小程序的完成讓人感覺比較舒心。

代碼實(shí)現(xiàn)如下：

#!/usr/bin/pythonfrom collections import Counterdef 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_valuedef 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_divisorprint(MaxDivisor(12,18))print(MaxDivisor(7,2))print(MaxDivisor(7,13))print(MaxDivisor(24,56))print(MaxDivisor(63,81))

程序的執(zhí)行結(jié)果如下：