欧拉函数

对于正整数n，欧拉函数phi(n)是小于等于n的数中与n互质的数的个数。

计算单个欧拉函数值一般使用公式求：phi(n) = n(1 - 1/p[1])(1 - 1/p[2])…(1 - 1/p[k])，其中p[i]为n的不同质因数。

int phi(int n) {
    int i, ans = n;
    for (i = 2; i * i <= n; i++) {
        if (0 == n % i) {
            ans = ans - ans / i;
            while (0 == n % i)
                n /= i;
        }
    }
    if (n > 1)
        ans = ans - ans / n;
    return ans;
}

如果要获得1~n区间内所有的欧拉函数值，可采用类似质数筛选的思想来做。有必要先介绍下欧拉函数的一些性质。

• 若n为质数，那么phi(n) = n-1。
• 若n = p^k，p为质数（即单个质数的幂），则phi(n) = (p-1)p^(k-1)。
• 若p与q互质，则phi(pq) = phi(p) * phi(q)。

由上述性质，可推导出两条定理：设p为质数，n为任意正整数，

• 若p为n的约数，则phi(np) = phi(n) * p
• 若p不为n的约数，则phi(np) = phi(n) * (p-1)

根据上述两条定理，可以枚举质数p来递推求解phi(np)，时间复杂度为O(n)。

pflag = [True] * (n+1)
plist = []
phi = [1] * (n+1)
for i in xrange(2, n + 1):
    if pflag[i]:
        plist.append(i)
        phi[i] = i - 1
    for j in plist:
        if i * j > n: break
        pflag[i] = False
        if i % j == 0:
            phi[i*j] = phi[i] * j
            break
        else:
            phi[i*j] = phi[i] * (j-1)
print phi