首页 > 代码库 > 求一个数的最大素因子(python实现)

求一个数的最大素因子(python实现)

2024-07-02 07:33:07   226人阅读

　　首先想到的是，将这个数进行素因子分解，得到所有的因子，然后取最大的。

　　首先写一个判断一个数是否是素数的方法：

　　

?
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];

　算法改进：

 


联系
我们