欧拉筛法（phi，d，prime）

筛法求素数的核心就是让每个合数被它的最小质因子筛掉，那么剩下来的就是素数了。

于是在这个过程中我们可以顺便求出每个数的φ（）、d（）、e（）。
ϕ:小于等于该数的与它互质的数的个数(一个数与其自身互质)d:该数的正因数个数e:该数最小质因数的个数
其中上述三个函数均为不完全积性函数（即当x、y互质时才有f(xy)=f(x)f(y)），因此在筛法筛这三个函数时要有分情况讨论。

当x、y不互质时，φ(xy)=φ(x) y，其中y是x最小质因数（即）。由φ的通式可得:φ(xy)=xy(1-1/p₁)(1-1/p₂)…=xφ(y)，所以在用最小素因子筛时就可求了。

当x、y不互质时,由d的通式（上百科自查吧）可得d(xy)=d(x)[e(x)+2]/[e(x)+1]。

当x、y不互质时，若x是y的最小质因数，则e(xy)=e(y)+1。

下面就是代码了——

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 }

原文链接: https://www.cnblogs.com/CXCXCXC/p/4934171.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍