首页 > 代码库 > noip知识点总结之--线性筛法及其拓展
noip知识点总结之--线性筛法及其拓展
一、线性筛法
众所周知。。。线性筛就是在O(n)的时间里找出所有素数的方法
code：
void get_prime(int N){ int i, j, k; memset(Flag, sizeof(Flag), 0); for (i = 2; i <= N; ++i){ if (!Flag[i]) p[++tot] = i; for (j = 1; j <= tot; ++j){ if ((k = i * p[j]) > N) break; Flag[k] = 1; if (!(i % p[j])) break; } }}
为什么这是线性的呢？
因为程序中利用了性质"每个合数必有一个最小素因子"，于是每个合数仅被它的最小素因子筛去正好一次，所以是线性时间。
每个合数仅被它的最小素因子筛去正好一次的体现在于：if (!(i % p[j])) break;
如果不理解的话可以手动算一下i = 2 to 15的情况就可以明白啦！
（p.s. 其实准确的复杂度是O(n * loglogn）的，但是loglogn趋近于一个常数）
二、利用线性筛法求欧拉函数
欧拉函数phi(n)的值定义为1到n中与n互质的数的个数。
如phi(1) = 1, phi(2) = 1, phi(3) = 2, phi(4) = 2, phi(5) = 4, phi(6) = 2...
那么如何利用线性筛来求呢？
我们需要知道以下性质（证略）：
（1）若n为质数，phi(n) = n - 1;
（2）若(n % a == 0 && (n / a) % a == 0) 则有：phi(n) = phi(n / a) * a;
（3）若(n % a == 0 && (n / a) % a != 0) 则有：phi(n) = phi(n / a) * (a - 1);
于是就可以做了，code：
1 void get_phi(int N){ 2 int i, j, k; 3 memset(Flag, sizeof(Flag), 0); 4 phi[1] = 1; 5 for (i = 2; i <= N; ++i){ 6 if (!Flag[i]) 7 p[++tot] = i, phi[i] = i - 1; 8 for (j = 1; j <= tot; ++j){ 9 if ((k = i * p[j]) > N) break;10 Flag[k] = 1;11 if (!(i % p[j])){12 phi[k] = phi[i] * p[j];13 break;14 }else15 phi[k] = phi[i] * (p[j] - 1);16 }17 }18 }
三、线性筛的其他应用 --计算Mobius函数μ[n]
首先我们定义μ[d]：
（1）若d = 1，那么μ[d] = 1
（2）若d = p1 * p2 * … * pr （r个不同质数，且次数都唯一）μ[d] = (-1) ^ r
（3）其余 μ[d] = 0
可以得到性质：
∑(d|n) μ[d] = 0 (n > 1)
而n = 1时，上式等于1
Mobius函数在积性函数的计算中非常重要，此处略过不讲。
利用上面提到的性质就可以求μ[n]了，code：
1 void get_u(int N){ 2 int i, j, k; 3 memset(Flag, sizeof(Flag), 0); 4 u[1] = 1; 5 for (i = 2; i <= N; ++i){ 6 if (!Flag[i]) 7 p[++tot] = i, u[i] = -1; 8 for (j = 1; j <= tot; ++j){ 9 if ((k = i * p[j]) <= N) break;10 Flag[k] = 1;11 if (!(i % p[j])){12 u[k] = 0; 13 break;14 }else u[k] = -u[i];15 }16 }17 }
noip知识点总结之--线性筛法及其拓展