题解 P5736 【【深基7.例2】质数筛】

UPDATE

2020-02-05 将速度是1/3改为3倍，感谢Stay_Hungry

其实不需要素数筛，不需要存入数组，一个素数判断就够了

#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倍，可以看一看

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和本身因数，不是素数