给定整数 n
,返回 所有小于非负整数 n
的质数的数量 。
示例 1:
输入:n = 10 输出:4 解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2:
输入:n = 0 输出:0
示例 3:
输入:n = 1 输出:0
提示:
0 <= n <= 5 * 106
class Solution {
public:int countPrimes(int n) {if (n <= 2) return 0; // 小于等于 2 的时候没有质数vector<bool> isPrime(n, true); // 创建一个布尔数组,初始值为 trueisPrime[0] = isPrime[1] = false; // 0 和 1 不是质数for (int i = 2; i * i < n; i++) { // 从 2 开始筛选质数if (isPrime[i]) {for (int j = i * i; j < n; j += i) {isPrime[j] = false; // 将 i 的倍数标记为 false}}}// 统计质数数量return count(isPrime.begin(), isPrime.end(), true);}
};
count
函数返回在指定范围内等于 value
的元素数量。
举例:n = 14
初始化布尔数组
首先创建一个布尔数组 isPrime
,大小为 14,并将所有元素初始化为 true
。同时,设置 isPrime[0]
和 isPrime[1]
为 false
(因为 0 和 1 不是质数)。
isPrime: [F, F, T, T, T, T, T, T, T, T, T, T, T, T]
开始筛选质数,从 2 开始。
第一次迭代:i = 2
isPrime[2]
为true
,表示 2 是质数。- 将 2 的倍数标记为
false
(从i * i = 4
开始):
isPrime: [F, F, T, T, F, T, F, T, F, T, F, T, F, T]
第二次迭代:i = 3
isPrime[3]
为true
,表示 3 是质数。- 将 3 的倍数标记为
false
(从i * i = 9
开始):
isPrime: [F, F, T, T, F, T, F, T, F, F, F, T, F, T]
第三次迭代:i = 4
i * i = 16
大于 14,所以不再需要进一步的筛选。
统计结果:总共有 6
个质数