质数,欧拉函数及莫比乌斯函数的快速线性筛选法，时间复杂度 $O(n)$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| const int MAXN = 100000;
int phi[MAXN + 10], prime[MAXN + 10], mu[MAXN + 10], tot;
bool vis[MAXN + 10];
inline void init() {
mu[1] = phi[1] = 1;
for (register int i = 2; i <= MAXN; i++) {
if (!vis[i]) prime[++tot] = i, phi[i] = i - 1, mu[i] = -1;
for (register int j = 1; j <= tot && i * prime[j] <= MAXN; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j], mu[i * prime[j]] = 0;
break;
} else phi[i * prime[j]] = phi[i] * (prime[j] - 1), mu[i * prime[j]] = -mu[i];
}
}
}
|
