欧拉phi函数

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 // 计算欧拉phi函数。phi(n)是不超过n且与n互素的正整数个数
 5 int euler_phi(int n){
 6     int m = (int)sqrt(n + 0.5);
 7     int ans = n;
 8     // phi(n)=n(1-1/p1)(1-1/p2)...(1-1/pk)
 9     for(int i = 2 ; i <= m ; i++) if(n % i == 0){
10         ans = ans / i * (i - 1);
11         while(n % i == 0) n /= i;
12     }
13     if(n > 1) ans = ans / n * (n - 1);
14     return ans;
15 }
16 // 用类似筛法的方式计算phi(1)、phi(2)、...、phi(n)
17 #define maxn 1000
18 int phi[maxn];
19 void phi_table(int n){
20     for(int i = 2 ; i <= n ; i++) phi[i] = 0;
21     phi[1] = 1;
22     for(int i = 2; i <= n ; i++) if(!phi[i])
23         for(int j = i ; j <= n ; j += i){
24             if(!phi[j]) phi[j] = j;
25             phi[j] = phi[j] / i * (i - 1);
26         }
27 }
28 int main(){
29     phi_table(999);
30     for(int i = 1 ; i <= 999 ; i++)
31         if(phi[i] != euler_phi(i))
32             printf("wrong at %d
",i);
33     return 0;
34 }