题解 | #质数的计数#

线性筛法

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int primesCount(int n) {
        // write code here
        // 筛选法
        vector<bool> flag(n);
        vector<int> primes;
        for (int i = 2; i < n; i ++ ) {
            if (!flag[i]) {
                primes.push_back(i);
            }
            for (int j = 0; primes[j] <= n / i; j ++ ) {
                flag[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
        return primes.size();
    }
};

时间复杂度：O(n)