欧拉函数算法

欧拉函数

 1 /*
 2     欧拉函数：
 3         小于或等于n的正整数中，与n互质的数的数目
 4 */ 
 5 #include<stdio.h>
 6 #define N 3000005
 7 __int64 ans[N];
 8 void init() //打表法 
 9 {
10     for(int i=1;i<N;i++) ans[i]=i;
11     for(int i=2;i<N;i+=2) ans[i]/=2;
12     for(int i=3;i<N;i+=2) 
13         if(ans[i]==i){
14             for(int j=i;j<N;j+=i) ans[j]=ans[j]/i*(i-1);
15         }
16 }
17 int euler(int n) //直接求法 
18 {
19     int ret=1;
20     for(int i=2;i*i<=n;i++){
21         if(n%i==0){
22             n/=i,ret*=i-1;
23             while(n%i==0){
24                 n/=i,ret*=i;
25             }
26         }
27     }
28     if(n>1) ret*=n-1;
29     return ret;
30 } 
31 int main(void)
32 {
33     int n;
34     while(scanf("%d",&n)!=EOF)
35     {
36         printf("%d
",euler(n));
37     }
38     return 0;
39 }

View Code

求欧拉函数算法

 1 2种求欧拉函数的算法
 2  1，
 3  void init()
 4   {
 5       __int64 i,j;
 6       e[1] = 1;
 7       for(i=2;i<=N;i++)
 8           if(!e[i])
 9           {             
10               for(j=i; j<=N; j+=i)
11               {    
12                  if (!e[j])
13                      e[j] = j;
14                  e[j] = e[j] / i * (i-1);
15             }    
16          }
17  }
18 
19 2，利用素数筛选：
20 void init()
21 {
22     __int64 i, j;
23     
24     p[0] = 1; //记录素数个数
25     p[1] = 2;
26     for (i=3; i<N; i+=2)
27     {
28         if (hash[i])
29             continue;
30         p[++p[0]] = i;
31         for (j=i*i; j<N; j+=i)
32             hash[j] = true;
33     } //筛素数
34     
35     e[1] = 1;
36 
37     for (i=1; i<=p[0]; i++)
38         e[p[i]] = p[i] - 1; //初始化素数的phi
39 
40     for (i=2; i<N; i++)
41     {
42         if(!e[i])
43         {
44             for (j=1; j<=p[0]; j++)
45                 if (i % p[j]==0)
46                 {
47                     if (i / p[j] % p[j])
48                         e[i] = e[i / p[j]] * e[p[j]];
49                     else
50                         e[i] = e[i / p[j] ]* p[j];
51                     break;
52                 } // 利用上述性质求解
53         }        
54     }
55     return ;
56 }
57 2，筛选法(求某一个数的)：
58 int euler(int x)
59 {
60     memset(a,0,sizeof(a));
61     int i,j;
62     for(i=2;i<=x;i++)
63     {
64         if(!a[i]&&x%i==0)//重点
65         {
66             for(j=i;j<x;j=j+i)
67                 a[j]=1;
68         }
69     }
70     int s=0;
71     for(i=1;i<x;i++)
72         if(!a[i]) s++;
73         return s;
74 }

View Code