leetcode 链接：204. 计数质数

题目

统计所有小于非负整数 n 的质数的数量。

示例：

  1. 输入：n = 10
  2. 输出：4
  3. 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
输入：n = 0
输出：0

输入：n = 1
输出：0

解答 & 代码

设置一个数组来记录各个数值是否为质数
从 2 开始遍历到 n - 1：

  • 如果当前数为质数，那么它的倍数都是合数，因此，将其倍数（< n）都置为 false
    class Solution {
public:
  int countPrimes(int n) {
      vector<bool> isPrime(n, true);
      int cnt = 0;
      for(int i = 2; i < n; ++i)
      {
          if(isPrime[i])    // 如果当前数为质数
          {
              ++cnt;        // 质数计数 +1
              // 将当前数的倍数都置为合数
              for(int j = 2 * i; j < n; j += i)
                  isPrime[j] = false;
          }
      }
      return cnt;
  }
};
    执行结果： ``` 执行结果：通过

执行用时：52 ms, 在所有 C++ 提交中击败了 93.02% 的用户 内存消耗：7.1 MB, 在所有 C++ 提交中击败了 67.51% 的用户 ```