算法-计数质数

题目：

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

思路：

使用埃式筛法

当n大于等于2时，如果当前遍历的数 i 是质数，那么从 i*i 开始，直到 n 为止，把 i 的倍数都标记为合数

代码：

class Solution {
public:
    int countPrimes(int n) {
        if(n <= 2) return 0;
        vector<bool> isPrime(n + 1, true);
        for(int i = 2; i < n; i++){
            if(isPrime[i]){
                for(int j = i; j <= n / i; j++){
                    isPrime[i * j] = false;
                }
            }
        }

        int res = 0;
        for(int i = 2; i < n; i++){
            if(isPrime[i]) res++;
        }

        return res;
    }
};