每天一道LeetCode-----计算小于n的素数个数

Count Primes

原题链接Count Primes

计算小于n的素数个数

思路：

如果一个数m是素数，那么所有m * k就都不是素数。另外2是最小的素数

代码如下

class Solution {
public:
    int countPrimes(int n) {
        vector<int> nums(n 1);
        int count{0};
        for(int i = 2; i < n; ++i) {
            if(nums[i]) {
                ++count;
                for(int j = 2; i * j < n; ++j) {
                    nums[i * j] = 0;
                }
            }
        }
        return count;
    }
};