目录
埃氏筛
埃氏筛是一种筛素数的方法,埃氏筛的思想很重要,主要是时间复杂度
朴素的埃氏筛的时间复杂度是\(O(nlogn)\)
这个复杂度是调和级数
vector<int>p;
int vis[N];
void solve()
{
rep(i,2,n){
if(!vis[i]) p.pb(i);
for(int j=i+i;j<=n;j+=i) vis[j]=1;
}
}
优化的埃氏筛的时间复杂度O(nloglogn)是很小的,基本上已经接近线性了
int vector<int>p;
vis[N];
void solve()
{
rep(i,2,n){
if(!vis[i]) p.pb(i);
for(int j=i+i;j<=n;j+=i) vis[j]=1;
}
}
线性筛
线性筛的时间复杂度之所以是线性,是因为每个数只会被它的最小素因子筛一次。
vector<int>p;
int vis[N];
void solve()
{
rep(i,2,n){
if(!vis[i]) p.pb(i);
for(int j=0;p[j]*i<=n;++j){
vis[p[j]*i]=1;
if(i%p[j]==0) break;
}
}
}
标签:埃氏,筛法,rep,int,质数,基础,vis,线性,复杂度
From: https://www.cnblogs.com/cxy8/p/18011717