概述：

欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数 n ，小于 n 且和 n
互质的正整数（包括 1）的个数，记作 φ(n) 。

本文主要探讨如何在线性时间内求得一个整数区域中每个数的欧拉函数值。

通式

代码如下：

int Euler(int n){
    int res = n,i;
    for(i=2;i * i <= n;i++)
    if(n%i == 0){
        n /=i ;
        res = res - res/i;
        while(n % i ==0)
            n/=i;
    }

    if (n > 1)   
        res = res - res/n; 

    return res;
}

求区域的欧拉函数值

从通式上看出，求一个数的欧拉函数的计算其实并不复杂，但是如果要求一个整数区域的欧拉函数值的话，对于每个整数都用通式去求未免太过复杂。事实上，假设p,q是个质数,那么我们不难发现对于φ(pq),它的值正好等于φ(p)*φ(q). 这其中的原理事实上也不难想象。那么也就是说，我们是否可以通过一些已有的欧拉函数值，来直接得到其他数的欧拉函数值？

这便是我们今天要来探讨的。在讨论这些前，我们先仔细分析一下欧拉函数的性质。

性质1

(1) 若n为素数，则φ(n) = n - 1

显然，由于n为素数，1~n-1与n都只有公因子1，因此φ(n) = n - 1。

性质2

(2) 若n = p^k，p为素数（即n为单个素数的整数幂），则φ(n) = (p-1)*p^(k-1)

因为n是p的整数幂，因此所有p的倍数和n都不互质。小于n的p的倍数一共有p^(k-1)-1个，因此和n互质的个数为：

p^k-1 - (p^(k-1)-1) = p^k - p^(k-1) = (p-1)*p^(k-1)

性质3

3) 若p和q互质，则φ(pq) = φ(p) \ φ(q)

此处建议手推一遍

对于所有小于pq的整数u，可以表示为u=aq+r。(a=0,1,2,…,p-1，r=0,1,…,q-1)。

对于u = aq + r, 设R = u mod p，0≤R<q。对于一个固定的r，设a1, a2满足0 <= a1, a2 < p且a1≠a2，有：

u1 = a1*q+r, u2 = a2*q+r
u1-u2=(a1-a2)*q

因为p与q互质，且|a1-a2|<p，则|u1-u2|一定不是p的倍数。

所以对于每一个固定的r，其对应的p个u = a*q+r(a=0,1,2,…,p-1)对mod p来说余数都不相同，即u mod p的结果恰好取遍0,1,…,p-1中的每一个数。

下面我证明一个引理：u mod p与p互质 <=> u与p互质，其证明如下：

假设a,b互质,c = a mod b。
假设c与b不互质，则存在d≥1，使得c=nd, b=md。
由于c = a mod b，因此a = kb + c，
则a = kmd + nd = (kn+m)d
因此d是a,b的公因数，与a,b互质矛盾。
假设不成立，所以c与b互质。

因此对于任意一个确定的r，与其对应的p个u中恰好有φ(p)个与p互质。

同理，由u = aq + r知r与q互质 <=> u与q互质。因此在0..q-1中恰好有φ(q)个r使得u与q互质。综上，当r与q互质的情况下，固定r可以得到φ(p)个与p和q都互质的数。

满足条件的r一共用φ(q)个，所以一共能找到有φ(p) * φ(q)个与p和q都互质的数。

由此得证：φ(p*q) = φ(p) * φ(q)

在上面这些性质的基础上我们能到推导出两条定理：

推导1

若p为质数，n为任意整数：

1) 若p为n的约数，则φ(np) = φ(n) p

若p为n的约数，且p为质数。则我们可以将n表示为p^k*m。m表示其他和p不同的质数的乘积。

显然有p^k与m互质，则：

φ(n) = φ(p^k)*φ(m) = (p-1)*p^(k-1)*φ(m)
φ(n*p) = φ(p^(k+1))*φ(m) = (p-1)*p^k*φ(m) = 
(p-1)*p^(k-1)*φ(m) * p =  φ(n) * p

推导2

2) 若p为不为n的约数，则φ(np) = φ(n) (p-1)

由p不为n的约数，因此p与n互质，所以φ(n*p) = φ(n) φ(p) = φ(n)(p-1)

根据这两条定理，当我们得到一个n时，可以枚举质数p来递推的求解φ(n*p)。这一步正是说明了我们只要在欧拉筛法的基础上修改即可。因为欧拉筛法的复杂度是线性的，所以求一个大区域的欧拉函数值的过程也是O(n).

伪代码如下：

isPrime[] = true
primeList = []
phi = []    // phi[n]表示n的欧拉函数
primeCount = 0
For i = 2 .. N
    If isPrime[i] Then
        primeCount = primeCount + 1
        primeList[ primeCount ] = i
        phi[i] = i - 1 // 质数的欧拉函数为p-1
    End If 
    For j = 1 .. primeCount
        If (i * primeList[j] > N) Then
            Break
        End If
        isPrime[ i * primeList[j] ] = false
        If (i % primeList[j] == 0) Then
            // primeList[j]是i的约数，φ(n*p) = φ(n) * p
            phi[ i * primeList[j] ] = phi[i] * primeList[j];
            Break
        Else 
            // primeList[j]不是i的约数，φ(n*p) = φ(n) * (p-1)
            phi[ i * primeList[j] ] = phi[i] * (primeList[j] - 1);
        End If
    End If
End For