首页 > 代码库 > [原博客] 关于线性筛
[原博客] 关于线性筛
埃氏筛法：从2开始，找到第一个没有被筛的数，把它标记为素数，然后把它的2倍、3倍……筛掉。
复杂度O(nlogn)。
改进的埃氏筛法：从2开始，找到第一个没有被筛的数x，把它标记为素数，然后把它的x倍、x+1倍……筛掉。
复杂度O(nloglogn)。
线性筛：保证每个数都被它的最小素因子筛掉。
复杂度O(n)。
C++写起来大概是这样的：
int mindiv[10000005],tot,prime[10000050];int main(){ for(int i=2;i<=10000000;i++){ if(!mindiv[i]){ mindiv[i]=i;prime[tot++]=i; } for(int j=0;prime[j]*i<=10000000;j++){ mindiv[prime[j]*i]=prime[j]; if(prime[j]==mindiv[i]) break; //! } } return 0;}
上述代码求得[1,1000w]的素数，本机Core i3运行用时0.14s，还是很快的。
其中,mindiv[x]保存了x的最小素因子，用它有很多用处（例如分解质因数什么的）。
筛积性函数
积性函数就是指：对于正整数n的一个算术函数 f(n)，且当a,b互质时f(ab)=f(a)f(b)。
如：欧拉函数，莫比乌斯函数。
下面以筛欧拉函数为例：
φ(x)表示1~x中与x互质的数的个数。
- 如果p为质数，φ(p)=p-1。
- 如果p为质数，φ(p^q)=p^k-p^(k-1)=(p-1)*p^(q-1)。
- φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。
- 若m,n互质，φ(mn)=φ(m)φ(n)。（积性）
- 当n为奇数时，φ(2n)=φ(n)。
这样我们就可以把所有数分成若干类：
- 质数。φ(p)=p-1。
- 最小质因子指数不为1。φ(i*p)=φ(i)*p。
- 最小质因子指数为1。φ(i*p)=φ(i)*φ(p)。
在筛素数的时候分别处理这三种情况即可。
1 int mindiv[10000005],tot,prime[10000050],phi[10000050]; 2 int main(){ 3 for(int i=2;i<=10000000;i++){ 4 if(!mindiv[i]){ 5 mindiv[i]=i;prime[tot++]=i;phi[i]=i-1;//1 6 } 7 for(int j=0;prime[j]*i<=10000000;j++){ 8 mindiv[prime[j]*i]=prime[j]; 9 if(prime[j]==mindiv[i]){10 phi[prime[j]*i]=phi[i]*prime[j] ;break;//211 }12 phi[prime[j]*i]=phi[i]*(prime[j]-1);//313 }14 }15 return 0;16 }
这样就求出了2~1000w的欧拉函数。
方便快捷。
[原博客] 关于线性筛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。