这道题是线性筛的模板题,所以我们考虑怎么不用线性筛。
我们都知道有一种筛法叫埃拉托色尼筛,简称埃氏筛,它比线性筛好写,也更好理解,但它过不了这道题,那怎么办呢?我们可以用 bitset 代替 bool 数组来进行优化,这造成的常数优化非常显著,以至于开了 ios::sync_with_stdio(false)
之后能轻松过掉这道题,和线性筛的时间总差距只有 0.5s,可以说是非常优秀了。
AC 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| #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; }
|