leetcode：204. 计数质数

题目

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

示例：

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

解答 & 代码

筛选法：

  1. 设立一个数组 isPrime: isPrime[i] 代表 i 是否为质数。初始化都为 true
  2. 令 i 从 2 开始遍历，直到 i < sqrt(n)。（由于因子的对称性，超过 sqrt(n) 后的两个乘数其实和之前重复）
    1. 如果当前数 i 是质数，那么 i*2, i*3, i*4, … 都不可能是质数，标为 false。实际上 i*2, i*3, … 已经被之前 i=2、i=3 的时候标记过了，因此从 i*i 开始标记即可
  3. 统计小于 n 的质数的个数

[中等] 204. 计数质数 - 图1

  1. class Solution {
  2. public:
  3.     int countPrimes(int n) {
  4.         if(n < 2)
  5.             return 0;
  7.         // 1. 数组 isPrime: isPrime[i] 代表 i 是否为质数。初始化都为 true
  8.         vector<bool> isPrime(n, true);
  9.         isPrime[0] = false;
  10.         isPrime[1] = false;
  11.         // 2. 从 2 开始遍历，直到 i < sqrt(n)。（由于因子的对称性，超过 sqrt(n) 后的两个乘数其实和之前重复）
  12.         for(int i = 2; i * i < n; ++i)
  13.         {
  14.             // 如果当前数 i 是质数，那么 i*2, i*3, i*4, ... 都不可能是质数，标为 false
  15.             if(isPrime[i])    
  16.             {
  17.                 // 实际上 i*2, i*3, ... 已经被之前 i=2、i=3 的时候标记过了，因此从 i*i 开始即可
  18.                 for(int j = i * i; j < n; j += i)
  19.                     isPrime[j] = false;
  20.             }
  21.         }
  23.         // 3. 统计小于 n 的质数的个数
  24.         int result = 0;
  25.         for(int i = 2; i < n; ++i)
  26.         {
  27.             if(isPrime[i])
  28.                 ++result;
  29.         }
  30.         return result;
  31.     }
  32. };

复杂度分析：

  • 时间复杂度[中等] 204. 计数质数 - 图2：操作数为 n/2 + n/3 + n/5 + n/7 + … = n × (1/2 + 1/3 + 1/5 + 1/7 + …)
  • 空间复杂度 O(n)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：180 ms, 在所有 C++ 提交中击败了 84.40% 的用户
  4. 内存消耗：9.9 MB, 在所有 C++ 提交中击败了 94.94% 的用户