计数质数

厄拉多塞筛法西元前250年，希腊数学家厄拉多塞(Eeatosthese)想到了一个非常美妙的质数筛法，质数的因子除了1就是它本身，因此从2开始的任意一个数x，x乘一个大于1的正整数得到的数字一定不是质数，根据这个原理，我们可以进行如下操作：

1. 要寻找到正整数n为止的质数个数，构造一个长度为n的向量output，output[i]表示正整数i是否是质数，初始化这个向量中所有的元素为1（True）。
2. output前两个数置零（1和2不是质数），遍历从2开始到suqare(n)+1范围内的所有正整数i，将output向量中所有是i的正整数倍（大于1）的数所在位置全部置零。
3. 循环结束后得到的output向量即可代表相应位置的每一个正整数是否为质数，求和即为结果。

class Solution {
public:
    int countPrimes(int n) {
        if(n<=2){
            return 0;
        }
      double base = sqrt(n);
        vector<int> ret(n,1);
        ret[0]=ret[1]=0;
        for(int i=2;i<base;++i){
            if(ret[i]==0)
                continue;

            for(int u=2*i; u < n; u+=i)
                ret[u] = 0;
        }
        int retn=0;
        for(int j=0;j<n;++j)
            retn+=ret[j];
        
        return retn;
    }
};

欧几里得筛法

所有偶数都不可能是质数，isPrime 表只记录奇数的可能性。

class Solution {
public:
    int countPrimes(int n) {
        int cnt=n>2?1:0;
        double base=sqrt(n);
        vector<bool> isPrime(n/2,true);
        for(int i=3;i<n;i+=2){// i represents real value
            if(isPrime[i/2]){
                cnt++;
                if(i<base){
                    for(int j=i*i;j<n;j+=2*i){//2*i 是保证结局是奇数。
                        isPrime[j/2]=false;
                    }
                }
            }
        }
        return cnt;
    }
};