线性筛

线性筛查找素数

#include<bits/stdc++.h>
using namespace std;

#define maxn 1000005
bool vis[maxn];
int p[maxn];
int tot;

//线性筛：每个合数仅被它的最小质因子筛过，且为一次
//线性筛找n以内的素数
void prime(int n)
{
    tot=0;
    memset(vis,1,sizeof(vis));
    vis[0]=vis[1]=false;
    for (int i=2; i<=n; i++)
    {
        if (vis[i])
            p[++tot]=i;
        for (int j=1; j<=tot&&p[j]*i<=n; j++)
        {
            vis[p[j]*i]=false;                          //合数被他的最小质因子筛掉
            if (i%p[j]==0)
                break;
        }
    }
}

//vis[p[j]*i]=false
//p[j]随j++体现为已出现的质数
//i是次次递增的要检测的数字，其具有次次+1的特点
//2*2=4筛4
//2%2==0停筛
//2*3=6筛6
//3*3=9筛9
//3%3==0停筛
//2*4=8
//4%2==0停
//2*5=10
//3*5=15
//5*5=25
//5%5==0停

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        prime(n);
        for(int i=1;i<=tot;i++)
        {
            cout<<p[i]<<endl;
        }
    }
    return 0;
}