欧拉筛法（phi，d，prime）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 200;
 4 int prime[N], e[N], d[N], tot, phi[N];
 5 bool not_p[N];
 6 inline void pre(){
 7     not_p[1] = 1;
 8     d[1] = 1;
 9     for(int i = 2; i < N; ++i){
10         if(!not_p[i]) {
11             ++tot, prime[tot] = i;
12             e[i] = 1, d[i] = 2; phi[i] = i - 1;
13         }
14         for(int j = 1; j <= tot; ++j){
15             int k = prime[j] * i;
16             if(k > N) break;
17             not_p[k] = 1;
18             if(i % prime[j]) {
19                 d[k] = d[i] * d[prime[j]];
20                 e[k] = 1;
21                 phi[k] = phi[i] * phi[prime[j]];
22             }
23             else{
24                 d[k] = d[i] / (e[i] + 1) * (e[i] + 2);
25                 e[k] = e[i] + 1;
26                 phi[k] = phi[i] * prime[j];
27                 break;
28             }
29         }
30     }
31 }
32 int main(){
33     pre();
34     printf("phi:\n");
35     for(int i = 1; i < N; ++i){
36         printf("%d\n", phi[i]);
37     }
38     printf("d:\n");
39     for(int i = 1; i < N; ++i){
40         printf("%d\n", d[i]);
41     }
42     printf("prime:\n");
43     for(int i = 1; i <= tot; ++i){
44         printf("%d\n", prime[i]);
45     }
46     return 0;
47 }