厄拉多塞筛法

厄拉多塞筛法主要用于查找一定范围内的素数的个数，速度比较快
C++

int countPrime(int n ){
int count=0;
vector<bool> signs(n,true);//假设初始都为素数
for (int i=2; i<n;i++){
     if(signs[i]){
         count++;
         for(int j=i+i; j<n;j+=i){
                signs[j]=false;

}}}
return count;
}

进一步优化使用比特表算法，布尔数组每个值占一个字节，4比特
可以使用一个比特来表示

int countPrime(int n ){
int count=0;
vector<bool> signs(n,true);//假设初始都为素数
····························································································································································································································································································+){
     if(signs[i]){
         count++;
         for(int j=i+i; j<n;j+=i){
                signs[j]=false;

}}}
return count;
}