🚩 题目链接
⛲ 题目描述
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0
提示：
0 <= n <= 5 * 106
🌟 求解思路&实现代码&运行结果
⚡ 埃氏筛
🥦 求解思路
- 最简单的思路就是枚举，判断每一个数是否能被1和本身的数整除，但是这种解法时间超限，需要改进。
- 埃氏筛：埃氏筛的基本概念大家可以参考官方题解补充相关的知识。基本思路就是，如果 x是质数，那么大于 x 的倍数 2x,3x,…2x,3x,… 一定不是质数，我们可以从这里入手，实现的过程中，我们需要额外维护一个标记数组，来判断当前数是否为质数。
- 线性筛：具体的求解以及证明的思路，大家可以参考官方题解。
- 有了基本的思路，接下来我们就来通过代码来实现一下递归和迭代的解法。
🥦 实现代码
class Solution {
public int countPrimes(int n) {
int[] isPrime = new int[n];
int ans = 0;
Arrays.fill(isPrime, 1);
for (int i = 2; i < n; i++) {
if (isPrime[i] == 1) {
ans++;
if ((long) i * i < n) {
for (int j = i * i; j < n; j += i) {
isPrime[j] = 0;
}
}
}
}
return ans;
}
}