求一个数的最大素因子(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]; |
算法改进：
文章来自：http://www.cnblogs.com/math-sushu/p/3702435.html