欧拉函数

欧拉函数φ(N)表示N 的欧拉函数：即小于N且与N互质数的个数

1.对于素数p, φ(p)=p-1，对于对两个素数p,q φ（pq）=pq-1

2.对于一个正整数N的素数幂分解N=P1^q1*P2^q2*...*Pn^qn.

φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn).

3.除了N=2,φ(N)都是偶数.

4.设N为正整数,∑φ(d)=N (d|N).

第一种求法的时间复杂度是 O( N* sqrt(N)) .

 1 //直接求解欧拉函数  
 2 int euler(int n){ //返回euler(n)   
 3      int res=n,a=n;  
 4      for(int i=2;i*i<=a;i++){  
 5          if(a%i==0){  
 6              //res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出   
 7              res -= res / i;
 8              while(a%i==0) a/=i;  
 9          }  
10      }  
11      if(a>1)  //res=res/a*(a-1);  
12           res -= res /i;
13      return res;  
14 }

还有种方法是在求素数的时候，顺便把欧拉函数的值给求了

 1 void Init(){     
 2      euler[1]=1;    
 3      for(int i=2;i<Max;i++)    
 4        euler[i]=i;    
 5      for(int i=2;i<Max;i++)    
 6         if(euler[i]==i)    
 7            for(int j=i;j<Max;j+=i)    
 8               //euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出     
 9               euler[j] -= euler[j] / i;
10 }

 1 //欧拉筛法,快速筛出1-100万的欧拉函数值
 2 void Eular()
 3 {
 4     for(int i=1;i<=maxn;i++) phi[i]=i;
 5     memset(isPrime,true,sizeof(isPrime));
 6     isPrime[0]=isPrime[1]=false;
 7     phi[1]=0;
 8     for(int i=2;i<=maxn;i++)
 9     {
10         if(isPrime[i])
11         {
12             for(int j=i;j<=maxn;j+=i)
13             {
14                 isPrime[j]=false;
15                 phi[j] -= phi[j]/i;
16             }
17         }
18     }
19 }