204. 计数质数

🟠   🔖  数组 数学 枚举 数论  🔗 力扣 LeetCode

题目

Given an integer n, return the number of prime numbers that are strictly less than n.

Example 1:

Input: n = 10

Output: 4

Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

Input: n = 0

Output: 0

Example 3:

Input: n = 1

Output: 0

Constraints:

• 0 <= n <= 5 * 10^6

题目大意

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

示例 1：

输入： n = 10

输出： 4

解释： 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入： n = 0

输出： 0

示例 3：

输入： n = 1

输出 ：0

提示：

• 0 <= n <= 5 * 10^6

解题思路

这是一个经典的筛法问题，可以用 埃拉托色尼筛法（Sieve of Eratosthenes）高效地解决。

1. 初始化状态数组：

   • 创建一个数组 seen，大小为 n，初始值为 0，用于标记数字是否为合数（非质数）。
   • 如果 seen[i] = 0，说明 i 是质数；如果 seen[i] = 1，说明 i 是合数。

2. 从最小的质数 2 开始筛选：

   • 遍历从 2 到 n-1 的每个数：
     • 如果当前数 i 是质数（seen[i] == 0），将其计入结果。
     • 从 i * i 开始，将所有 i 的倍数标记为合数（seen[j] = 1）。

3. 提前优化筛选范围：

   • 由于小于 i * i 的倍数在之前已经被其他质数标记过，因此从 i * i 开始筛选。

4. 统计质数个数：

   • 遍历 seen 数组，计算未被标记的数（质数）的数量。

5. 返回结果：

   • 返回计数值 res。

复杂度分析

• 时间复杂度：O(n log log n)，外层循环遍历所有数 2 到 n-1，但每个数的倍数最多被标记一次，因此整体复杂度为 O(n log log n)。
• 空间复杂度：O(n)，使用一个大小为 n 的数组 seen 来标记数字。

代码

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function (n) {
	let res = 0;
	let seen = new Array(n).fill(0);

	// 遍历从 2 到 n-1 的所有数
	for (let i = 2; i < n; i++) {
		if (seen[i]) continue; // 如果已标记为合数，跳过

		res++; // 当前数是质数
		for (let j = i * i; j < n; j += i) {
			seen[j] = 1; // 标记所有 i 的倍数为合数
		}
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
263	丑数	[✓]	数学	🟢	🀄️ 🔗
264	丑数 II	[✓]	哈希表 数学 动态规划 1+	🟠	🀄️ 🔗
279	完全平方数	[✓]	广度优先搜索 数学 动态规划	🟠	🀄️ 🔗
2427	公因子的数目		数学 枚举 数论	🟢	🀄️ 🔗
2761	和等于目标值的质数对		数组 数学 枚举 1+	🟠	🀄️ 🔗
3233	统计不是特殊数字的数字数量		数组 数学 数论	🟠	🀄️ 🔗