欧拉函数

1 /* 2     欧拉函数： 3         小于或等于n的正整数中，与n互质的数的数目 4 */  5 #include
      
        6 #define N 3000005 7 __int64 ans[N]; 8 void init() //打表法  9 {10     for(int i=1;i
       
        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\n",euler(n));37     }38     return 0;39 }
       
      

 求欧拉函数算法

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