埃氏筛选与线性筛选求素数

红太狼 2022-08-03 14:51 231阅读 0赞

//埃氏筛选法 复杂度O(nlognlogn)
    #include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;
        char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    const int N=2000010;
    bool vis[N];
    //bitset<N> vis;
    int prime[150010];
    
    int main()
    {
    
       // vis.set();
       //多次求素数的话要初始化
        int p=1;
        prime[0]=2;
        for(int i=3;i<=N;i+=2)
        {
            if(!vis[i])
            {
                prime[p++]=i;
                for(int j=i*2;j<=N;j+=i)
                {
                    vis[j]=1;
    
                }
            }
        }
        int n;
        while(~scanf("%d",&n) && n)
        {
            int i=0;
            while(prime[i]<=n)
            {
                printf("%d ",prime[i]);
                ++i;
            }
            putchar('\n');
        }
    
        return 0;
    }

下面的是线性筛选算法，与埃氏筛选相比，对于每个不是素数的数，这个算法只把它筛一次，不会多次筛掉，而埃氏筛选会多次筛掉。

分别用它们算了一下一亿以内素数的个数，埃氏筛选用时4-5秒的样子，而这个不到两秒。另外不知道为啥，用bitset代替bool数组比较慢，

但是bitset显著减少了内存使用。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;
        char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=2000010;
    //bitset <N>vis;
    bool vis[N];
    int prime[150000];
    int main()
    {
        int p=-1;
        //如果多次求素数的话要每次初始化vis
        for(int i=2;i<=N;i++)
        {
            if(!vis[i])prime[++p]=i;
            for(int j=0;j<=p && prime[j]*i<=N;j++)
            {
                vis[prime[j]*i]=1;
                if(i%prime[j]==0)break;
            }
        }
        int n;
        while(~scanf("%d",&n) && n)
        {
            int i=0;
            while(prime[i]<=n)
            {
                printf("%d ",prime[i]);
                ++i;
            }
            putchar('\n');
        }
        return 0;
    }