欧拉函数

欧拉函数是小于n的正整数中与 n 互质的数的数目，其中规定 φ(1) = 1。比如 φ(8) = 4 (1,3,5,7 和 8 互质)，φ(9) = 5 (1,2,4,5,7,8 和 9 互质)。

求欧拉函数的公式是

这个公式就是这个意思 ：φ(n) = n * (1 - 1 / p1) * (1 - 1 / p2) * (1 - 1 / p3) * ……  * (1 - 1 / pi)，pi是 n 的质因数。那么如何编程求欧拉函数呢？

还得知道这么个式子：n = p1 ^ a1 * p2 ^ a2 * p3 ^ a3*……* pi ^ ai，(p 是不大于 n 的素数，ai ≥ 0)，这个叫做 n 的标准分解式。所以我们只要从2开始枚举n的质因数pi，并将pi的ai次方全部除掉，然后接着枚举，这样欧拉函数就求出来了，这应该是个 O(n) 的复杂度。

当然这个可以改进到 O(logn)，只要枚举到sqrt(n)就行，因为大于等于sqrt(n) 的质因数至多只有一个，为什么呢？可以用反证法，若存在两个质因数都大于等于 n，根据上面的 n 的标准分解式，这两个质因数一定能相乘，而积却大于 n，所以不可能同时存在两个质因数同时大于 n。

最后发一下代码

    scanf("%d", &n);
    ans = n;
    for(int i = 2; i * i <= n; ++i)    //枚举 n 的质因数 
    {
        if(n % i == 0)
            ans = ans / i * (i - 1);    //公式 ，先除再乘是为了防止溢出
        while(n % i == 0) n /= i;    //将 pi ^ ai 都删去 
    }
    if(n > 1) ans = ans / n * (n - 1);    //判断是否存在一个质因数大于 sqrt(n) 
    printf("%d
", ans);