线性筛素数

前言：

一道数学题，最难想的小奥部分做对了，最后败在了筛素数（用了最质朴的方法
食用须知：文字解释较少，内容全面，仅作复习/归纳，时间充裕的初学者谨慎食用

Q：求n以内的素数

A：

1.朴素

• 思路：判断每一个数是否质数

• 时间复杂度：O(nsqrt(n))

• 代码：

#include <bits/stdc++.h>
using namespace std;
int n,cnt,keep[10005];
bool judge(int x)
{
    if(x==1) return 0;
    if(x==2) return 1;
    for(int j=2;j*j<=x;++j){if(x%j==0) return 0;}
    return 1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        if(judge(i)) keep[++cnt]=i;
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;++i) printf("%d ",keep[i]);
    return 0;
}

2.埃氏筛法

• 思路：每筛出一个质数，就标记n以内此素数的倍数不能选

• 时间复杂度：O(nloglogn)

• 代码：

#include <bits/stdc++.h>
using namespace std;
int n,cnt,keep[100005],temp[100005];
void sieve(int x)
{
    temp[0]=temp[1]=1;
    for(int i=2;i<=x;++i)
        if(!temp[i])
        {
            keep[++cnt]=i;
            for(int j=i+i;j<=x;j+=i) temp[j]=1;
        }
}
int main()
{
    scanf("%d",&n);
    sieve(n);
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;++i) printf("%d ",keep[i]);
    return 0;
}

3.欧拉筛法

• 思路：和2.埃氏筛法略有相似；任何合数都能表示成多个素数的积，枚举最小质因子之积从而标记不可选的数

• 时间复杂度：o(n)

• 代码：

#include <bits/stdc++.h>
using namespace std;
int n,cnt,keep[100005],vis[100005];
void sieve(int x)
{
    for(int i=2;i<=x;++i)
    {
        if(!vis[i]) keep[++cnt]=i;
        for(int j=1;j<=cnt,i*keep[j]<=x;++j)
        {
            vis[i*keep[j]]=1;//不能与下一句调换位置
            if(i%keep[j]==0) break;//当i是keep[j]的整数倍时（i%keep[j] == 0），i*keep[j+1]肯定被筛过，跳出循环
        }
    }
}
int main()
{
    scanf("%d",&n);
    sieve(n);
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;++i) printf("%d ",keep[i]);
    return 0;
}

后记：

• 筛素数是一项必备工具
• 朴素做法是必须写会的
• 后两种思想相似，思维方向不同
• 感性理解欧拉筛法