Euler function

欧拉函数

定义

欧拉函数：对于一个正整数n，小于或等于n的正整数中与n互质的正整数个数（包括1）的个数，记作 φ ( n )

例如euler(8)=4，因为1,3,5,7均和8互质。

求解方式

Euler函数表达通式：euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1,p2……pn为x的所有素因数，x是不为0的整数。euler(1)=1（唯一和1互质的数就是1本身）。

int euler(int n){ //返回euler(n) 
     int res=n,a=n;
     for(int i=2;i*i<=a;i++){
         if(a%i==0){
             res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出 
             while(a%i==0) a/=i;
         }
     }
     if(a>1) res=res/a*(a-1);
     return res;
}

补充

欧拉公式的延伸：

一个数的所有质因子之和是euler(n)*n/2。

欧拉定理：

对于互质的正整数a和n，有aφ(n) ≡ 1 mod n。

性质

(1).欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
(2).若n是质数p的k次幂，φ(n)=p^k-p(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
特殊性质：当n为奇数时，φ(2n)=φ(n)
(3).设a为N的质因数，若(N % a == 0 && (N / a) % a == 0) 则有E(N)=E(N / a) * a；若(N % a == 0 && (N / a) % a != 0) 则有：E(N) = E(N / a) * (a - 1)。
(4).若n为质数，则φ ( n ) = n - 1;

欧拉函数打表

可以得到关于欧拉函数的递推关系：
假设素数p能整除n，那么
如果p还能整除n / p, PHI(n) = PHI(n / p) * p;
如果p不能整除n / p, PHI(n) = PHI(n / p) * (p - 1);

#define Max 1000001
int euler[Max];
void Init() {
    euler[1] = 1;
    for (int i = 2; i < Max; i++)
        euler[i] = i;
    for (int i = 2; i < Max; i++)
        if (euler[i] == i)
            for (int j = i; j < Max; j += i)
                euler[j] = euler[j] / i *
                           (i - 1);  // 先进行除法是为了防止中间数据的溢出
}