时间复杂度O(n)
复制代码
1
2
3
4
5
6
7
8
9
10
11
12int tab[N],num=0; bool notzhi[N]={1,1}; for(int i=2;i<=N;++i){ if (notzhi[i]==0) tab[num++]=i; for(int j=0;j<num&&i*tab[j]<=N;++j){ notzhi[i*tab[j]]=1; if (i%tab[j]==0) break; } }
这样子能保证每个合数一定被最小质因子给筛掉，而且仅被筛一次，从而保证复杂度为O(n)
转载于:https://www.cnblogs.com/abclzr/p/5297758.html
最后
以上就是小巧小熊猫最近收集整理的关于质数的快速筛法的全部内容，更多相关质数内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复