素数筛法及线性筛求积性函数值学习笔记

定义

  • 快速求出 1 n1 ~ n 中所有素数的方法。

埃氏筛

1
2
3
4
5
6
7
8

bool not_prime[1005];
memset(not_prime, 0, sizeof(not_prime));
not_prime[1] = true;
for(int i = 2; i <= n; i++)
if(!not_prime[i])
for(int j = i + i; j <= n; j += i)
not_prime[j] = true;

枚举每一个质数的倍数,并将其打上标记,时间复杂度为 OnloglognO{nloglogn}

欧拉筛

为了达到线性筛 O(n)O(n) 的复杂度,每个数都只能被筛掉一次。

xx 质因数分解,写为 x=p1r1p2r2pkrkx = p_1^{r_1} \cdot p_2^{r_2} \cdots p_k^{r_k} ,假设 p1<p2<<pkp_1 < p_2 < \cdots < p_k ,需要每个数都只被其最小的质因子 p1p_1 筛掉。

将已经筛出来的质数存在质数表里,对于一个数 ii ,从指数表逐一取出质数 pjp_j ,将 iipjp_j 倍筛去,直至 iipjp_j 的倍数或筛完质数表内的所有质数倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int prime[1005], pcnt;
bool not_prime[10005];
void euler(int n) {
not_prime[1] = true;
for(int i = 1; i <= n; i++) {
if(!not_prime[i]) prime[++pcnt] = i;
for(int j = 1; j <= pcnt; j++) {
int v = i * prime[j];
if(v > n) break;
not_prime[v] = true;
if(i % prime[j] == 0) break;
}
}
}

这样就保证了每一个数都只被最小的质因子晒掉,时间复杂度为 O(n)O(n)

线性筛求积性函数值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int prime[1005], pcnt;
int phi[MAXN], mu[MAXN]
bool not_prime[MAXN];
void euler(int n) {
not_prime[1] = true;
phi[1] = 1, mu[1] = 1;
for(int i = 1; i <= n; i++) {
if(!not_prime[i]) {
prime[++pcnt] = i;
phi[a] = a - 1;
mu[a] = -1;
}
for(int j = 1; j <= pcnt; j++) {
int v = i * prime[j];
if(v > n) break;
not_prime[v] = true;
if(a % prime[j] == 0) {
phi[v] = phi[i] * prime[j];
mu[v] = 0;
}
else {
phi[v] = phi[i] * phi[prime[j]];
mu[v] = mu[i] * mu[prime[j]];
}
if(i % prime[j] == 0) break;
}
}
}

时间复杂度还是 O(n)O(n)