P3383【模板】线性筛 题解

· · 个人记录

这道题是线性筛的模板题，所以我们考虑怎么不用线性筛。

我们都知道有一种筛法叫埃拉托色尼筛，简称埃氏筛，它比线性筛好写，也更好理解，但它过不了这道题，那怎么办呢？我们可以用 bitset 代替 bool 数组来进行优化，这造成的常数优化非常显著，以至于开了 ios::sync_with_stdio(false) 之后能轻松过掉这道题，和线性筛的时间总差距只有 0.5s，可以说是非常优秀了。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000000;
int cnt=0,prime[6000000];
bitset<100000000> p;
void init() {
    p.flip();p[1]=0;
    for(int i=2;i<MAXN;i++) {
        if(p[i]) {
            prime[++cnt]=i;
            for(int j=i+i;j<MAXN;j+=i)
                p[j]=0;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    init();
    int n;
    cin>>n>>n;
    while(n--) {
        int x;
        cin>>x;
        cout<<prime[x]<<endl;
    }
    return 0;
}