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

jerryxjr1220

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

# 生成质数列表
def getPrime(n):
    primes = [True]*n
    primes[0], primes[1] = False, False
    for (i, prime) in enumerate(primes):
        if prime:
            for j in range(i*i,n,i):
                primes[j] = False
    primelist = []
    for (k, trueprime) in enumerate(primes):
        if trueprime:
            primelist.append(k)
    return primelist

# 生成欧拉函数列表
def philist(n):
    primelist = getPrime(n)
    PHI = [0]*(n+1)
    PHI[0], PHI[1] = -1, 1
    for eachprime in primelist:
        PHI[eachprime] = eachprime - 1
    for i in range(len(primelist)):
        p = primelist[i]
        for k in range(p*p,n+1,p):
                PHI[k] = PHI[int(k/p)]*(p-1)
        for j in range(p*p,n+1,p*p):
            PHI[j] = PHI[int(j/p)]*p
    return PHI

jerryxjr1220

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