Python實(shí)現(xiàn)的質(zhì)因式分解算法示例

2020-01-04 15:15:05

字體：大中小

供稿：網(wǎng)友

本文實(shí)例講述了Python實(shí)現(xiàn)的質(zhì)因式分解算法。分享給大家供大家參考，具體如下：

本來(lái)想實(shí)現(xiàn)一個(gè)其它的基本數(shù)學(xué)算法問(wèn)題，但是發(fā)現(xiàn)在實(shí)現(xiàn)之前必須得先完成分解質(zhì)因式的算法。

沒(méi)有去網(wǎng)上尋找什么比較好的求解算法，純粹是按照自己的理解寫(xiě)了一個(gè)試探性求解算法。也就是在MIT公開(kāi)課中教授提到的guess-try方法。代碼實(shí)現(xiàn)如下：

#!/usr/bin/pythondef PrimeNum(num):   r_value =[]   for i inrange(2,num+1):      for jin range(2,i):         ifi % j == 0:            break      else:         r_value.append(i)   returnr_valuedef PrimeFactorSolve(num,prime_list):   for n inprime_list:      ifnum % n == 0:         return[n,num / n]def PrimeDivisor(num):   prime_range= PrimeNum(num)   ret_vale =[]   while numnot in prime_range:      factor_list= PrimeFactorSolve(num,prime_range)      ret_vale.append(factor_list[0])      num =factor_list[1]   else:      ret_vale.append(num)   printret_valePrimeDivisor(120)

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