题目
- 计数质数
统计所有小于非负整数 n 的质数的数量。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。示例 2：
输入：n = 0
输出：0示例 3：
输入：n = 1
输出：0提示：
0 <= n <= 5 * 106题解
方法一：暴力遍历法
思路：遍历小于n的整数，每次判断是不是质数，若是质数，则将结果+1，最后返回结果（由于暴力超时，所以此处不列代码）
方法二：标记法
思路：创建一个大小为n的Boolean数组，其下标代表整数，从3开始遍历，由于大于3的偶数肯定不是质数，所以每次遍历+2，每次遍历，判断数组对应下表的值，若为false，则说明为质数，然后将此下标的奇数倍也全部标记为true（为合数），然后将结果result加1，统计最后的结果
class Solution {
public int countPrimes(int n) {
int result = 0;
boolean[] b = new boolean[n]; // 初始化默认值都为 false，为质数标记
if(2 < n) result++; // 如果大于 2 则一定拥有 2 这个质数
for(int i = 3; i < n; i += 2){ // 从 3 开始遍历，且只遍历奇数
if(!b[i]){ // 是质数
for(int j = 3; i * j < n; j += 2){
b[i * j] = true; // 将当前质数的奇数倍都设置成非质数标记 true
}
result++; // 质数个数 +1
}
}
return result;
}
}
