题解 P5736 【【深基7.例2】质数筛】
HsKr
2020-02-04 22:40:37
UPDATE
2020-02-05 将速度是1/3改为3倍，感谢[Stay_Hungry](https://www.luogu.com.cn/user/105922)
其实不需要素数筛，不需要存入数组，一个素数判断就够了
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
bool isprime(int x){//判断是否素数
if(x<=1) return false;//如果小于2，一定不是素数
for(int i=2;i<=sqrt(x);i++){//为什么要到sqrt(x)呢，因为如果有一个大于sqrt(n)的数可以被n整除，那么必有一个数n/i也可以被n整除且小于i
if(x%i==0) return false;//如果可以整除，那么不是素数
}
return true;//是素数
}
int main(){
int n,a;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
if(isprime(a)){
cout<<a<<" ";//是素数，就输出
}
}
return 0;
}
```
其实还可以优化，这里有一个优化的代码，速度是上面的$3$倍，可以看一看
```cpp
bool isprime(int n){
if(n<=1) return false;
if(n==2||n==3) return true;
if(n%6!=1&&n%6!=5) return false;
for(int i=5;i*i<=n;i+=6) if(n%i==0||n%(i+2)==0) return false;
return true;
}
```
除2,3外，其他所有素数都必须是$6n+1$或$6n+5$，因为$6n+2=2(3n+1)$，$6n+3=3(2n+1)$，$6n+4=2(3n+2)$，都有非1和本身因数，不是素数