首页 > 代码库 > 求一个数的最大素因子(python实现)
求一个数的最大素因子(python实现)
首先想到的是,将这个数进行素因子分解,得到所有的因子,然后取最大的。
首先写一个判断一个数是否是素数的方法:
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #judge a number whether a prime def judgePrime( self ,number,pme): if number < 2 : return False ; if number = = 2 : return True ; for p in pme: if p = = 2 : continue ; Q = number / p; R = number % p; if R = = 0 : return False ; else : if Q < p: return True ; else : continue ; |
然后求出所有比这个数的平方根小的素数:
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #get all Prime under a number,include this number def getPrimeUnderNumber( self ,number): pme = []; #definite a prime list pme.append( 2 ); pme.append( 3 ); if number < 5 : print ‘please input a number above 5‘ ; return ; i = 5 ; while i < = number: flag = self .judgePrime(i,pme); if flag: pme.append(i); i = i + 2 ; else : i = i + 2 ; return pme; |
分解素因子
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | # decomposition factors def getDecompositionFactors( self ,number): if math.sqrt(number) < 5 : primeList = self .getPrimeUnderNumber( 5 ); else : primeList = self .getPrimeUnderNumber(math.sqrt(number)); if number = = 2 or number = = 3 : return number; i = 0 ; pmeList = []; while number ! = 1 : p = number / primeList[i]; r = number % primeList[i]; if r = = 0 : pmeList.append(primeList[i]); number = p; else : if p < primeList[i]: pmeList.append(number); return pmeList; else : i = i + 1 ; return pmeList; |
最后获得最大素因子
?
1 2 3 4 5 6 7 8 9 10 | def getTheLargestPrimeFactorOfNumber( self ,number): start = clock(); pmeList = self .getDecompositionFactors(number); end = clock(); print end - start; return pmeList[ len (pmeList) - 1 ]; |
算法改进:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。