【Python库】Project Euler常用函数汇总

jerryxjr1220

由于计算Project Euler时经常会用到一些常用的函数，特此汇总一下，方便以后调用。

1. 
   
2. # 生成质数列表
   
3. def getPrime(n):
   
4.     primes = [True]*n
   
5.     primes[0], primes[1] = False, False
   
6.     for (i, prime) in enumerate(primes):
   
7.         if prime:
   
8.             for j in range(i*i,n,i):
   
9.                 primes[j] = False
   
10.     primelist = []
    
11.     for (k, trueprime) in enumerate(primes):
    
12.         if trueprime:
    
13.             primelist.append(k)
    
14.     return primelist
    
15. 
    
16. # 生成欧拉函数列表
    
17. def philist(n):
    
18.     primelist = getPrime(n)
    
19.     PHI = [0]*(n+1)
    
20.     PHI[0], PHI[1] = -1, 1
    
21.     for eachprime in primelist:
    
22.         PHI[eachprime] = eachprime - 1
    
23.     for i in range(len(primelist)):
    
24.         p = primelist[i]
    
25.         for k in range(p*p,n+1,p):
    
26.                 PHI[k] = PHI[int(k/p)]*(p-1)
    
27.         for j in range(p*p,n+1,p*p):
    
28.             PHI[j] = PHI[int(j/p)]*p
    
29.     return PHI
    

复制代码

jerryxjr1220

另外phi（n）还有个算法，可以参考
当n为质数：
Phi(n) = n-1
当p，q为质数时：
n = p * q
Phi(n) = （n-1） - （p-1） - （q-1）