欧拉筛

佚名 6年前 (2019-05-14) 随笔 1665人围观抢沙发百度已收录

直接上代码：

#include<iostream>
#include<bitset>
#include<cstring>
using namespace std;
const int maxn=1e5+50;
bool vis[maxn];
int prime[maxn];
void solve()
{
    int cnt=1;
    for(int i=2;i<=10000;i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
        }
        for(int j=1;j<cnt&&prime[j]*i<=10000;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
    for(int i=1;i<cnt;i++) cout<<prime[i]<<endl;
}
int main()
{
    solve();
    return 0;
}