素数筛法及线性筛求积性函数值学习笔记
定义
- 快速求出 1 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;
|
枚举每一个质数的倍数,并将其打上标记,时间复杂度为 Onloglogn 。
欧拉筛
为了达到线性筛 O(n) 的复杂度,每个数都只能被筛掉一次。
将 x 质因数分解,写为 x=p1r1⋅p2r2⋯pkrk ,假设 p1<p2<⋯<pk ,需要每个数都只被其最小的质因子 p1 筛掉。
将已经筛出来的质数存在质数表里,对于一个数 i ,从指数表逐一取出质数 pj ,将 i 的 pj 倍筛去,直至 i 为 pj 的倍数或筛完质数表内的所有质数倍。
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) 。
线性筛求积性函数值
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)