@[ZiruiLIU](/user/1128297) 你的线性筛一点都不线性，建议先学习一遍
by IceKylin @ 2024-02-28 19:52:08
@[ZiruiLIU](/user/1128297) 看了一下，你既然是这样的水平，那就脚踏实地的去刷入门，然后再来刷橙
by 菜のcrzOvO @ 2024-02-28 19:55:28
@[ZiruiLIU](/user/1128297) 上一帖子里回复不是说了嘛……
> 最后时间复杂度不对经……这是欧拉筛的板子，埃氏筛要是不用bitset卡的话似乎是过不去的，另外输入输出优化也要加上不然似乎也不过（我拿我自己的板子试了一下，#3和#5都T了）
by ACaCaca_ @ 2024-02-28 20:08:44
这个“线性筛”会把重复的质数遍历多次（如6同时被2和3遍历到）建议先学习一遍
建议：这个s数组开到1e8虽然没有问题，但在实际中尽量不要这么做。可以开个vector，遇到质数直接存里面，（1e8内质数个数<3e7）查询的时候直接根据下标拿出来就好了。
by codingwen @ 2024-02-28 20:09:13
如果不知道什么是vector，也建议学习一下，很有用
by codingwen @ 2024-02-28 20:09:59
- ```sqrt(n)```太慢，应该这么写：```i*i<=n```
- 埃氏筛能过，代码如下：
```cpp
#include <cstdio>
using namespace std;
const int N=1e8+5,M=1e7+5;
bool a[N];
int prime[M];
int main()
{
int n,q,cur=0;
scanf("%d%d",&n,&q);
a[0]=a[1]=true;
for(int i=2;i*i<=n;i++)
if(!a[i])
for(int j=2;i*j<=n;j++)
a[i*j]=true;
for(int i=2;i<=n;i++)
if(!a[i])
prime[++cur]=i;
while(q--)
{
int tmp;
scanf("%d",&tmp);
printf("%d\n",prime[tmp]);
}
return 0;
}
```
- 埃氏筛毕竟不是正解，请自行学习欧拉筛。
by return_second @ 2024-02-28 20:17:52
```cpp
这个“线性筛”会把重复的质数遍历多次（如6同时被2和3遍历到）建议先学习一遍
```
改为
```cpp
这个“线性筛”会把某些合数遍历多次（如6同时被2和3遍历到）建议先学习一遍
```
by codingwen @ 2024-02-28 20:18:24
@[return_second](/user/1047309) 似乎使用sqrt()不会太慢吧，[证据](https://www.luogu.com.cn/record/148678481)，编译器会识别这样的反复调用，然后优化一下，不会重复计算的（不吸氧气也可以过）
by syp11 @ 2024-02-28 21:25:50
@[ZiruiLIU](/user/1128297) 经过我卡了卡常，发现埃氏筛也是可以过的，但是最好去学一下欧拉筛，然后有几个常数问题需要注意一下
第一个是没必要把s数组全部赋值成1，如果1表示被筛掉了，0表示没有被筛掉，也是可以的
第二个是输入输出优化，不懂得话可以去搜一下，用流输入输出不解绑的话时间差的挺多的，这是板子，写在开头
```cpp
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
```
第三个是换行，可以输出"\n"而不是用endl，因为endl会不断刷新缓冲区，跑得慢（不懂得话及记结论）
第四个是没必要每次询问都把全体数访问一遍，可以开一个数组专门记所有的素数
最后把改好的代码发一下，这个是可以过的
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n, q, k, b;
bool s[100000010];
int prime[5761456],cnt;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=2;i<=sqrt(n);i++)
{
if(s[i]==0)
{
for(int j=2;j*i<=n;j++)
{
s[j*i]=1;
}
}
}
for(int i=2;i<=n;i++)
{
if(s[i]==0)
{
prime[++cnt]=i;
}
}
for(int i=1;i<=q;i++)
{
cin>>k;
cout<<prime[k]<<"\n";
}
return 0;
}
```
by syp11 @ 2024-02-28 21:37:32
@[return_second](/user/1047309)
线性筛可以的
你这个还有3个THL
by 52hertz_yh @ 2024-03-22 17:57:08