【Python库】Project Euler常用函数汇总
本帖最后由 jerryxjr1220 于 2016-10-16 09:48 编辑由于计算Project Euler时经常会用到一些常用的函数，特此汇总一下，方便以后调用。
# 生成质数列表
def getPrime(n):
primes = *n
primes, primes = False, False
for (i, prime) in enumerate(primes):
if prime:
for j in range(i*i,n,i):
primes = False
primelist = []
for (k, trueprime) in enumerate(primes):
if trueprime:
primelist.append(k)
return primelist
# 生成欧拉函数列表
def philist(n):
primelist = getPrime(n)
PHI = *(n+1)
PHI, PHI = -1, 1
for eachprime in primelist:
PHI = eachprime - 1
for i in range(len(primelist)):
p = primelist
for k in range(p*p,n+1,p):
PHI = PHI*(p-1)
for j in range(p*p,n+1,p*p):
PHI = PHI*p
return PHI
另外phi（n）还有个算法，可以参考
当n为质数：
Phi(n) = n-1
当p，q为质数时：
n = p * q
Phi(n) = （n-1） - （p-1） - （q-1）
页:
[1]