统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
思路
这道题给定一个非负数n，让我们求小于n的质数的个数，题目中给了充足的提示，解题方法就在第二个提示埃拉托斯特尼筛法Sieve of Eratosthenes中，这个算法的过程如下图所示，我们从2开始遍历到根号n，先找到第一个质数2，然后将其所有的倍数全部标记出来，然后到下一个质数3，标记其所有倍数，一次类推，直到根号n，此时数组中未被标记的数字就是质数。我们需要一个n-1长度的bool型数组来记录每个数字是否被标记，长度为n-1的原因是题目说是小于n的质数个数，并不包括n。 然后我们用两个for循环来实现埃拉托斯特尼筛法，难度并不是很大，代码如下所示：
image
代码实现
class Solution {
public int countPrimes(int n) {
if (n == 0) return 0;
boolean[] arr = new boolean[n];
for (int i = 0; i < n; i++) {
arr[i] = true;
}
arr[0] = false;
int count = 0;
int limit = (int)Math.sqrt(n);
// 埃拉托斯特尼筛法
for (int i = 2; i <= limit; i++) {
if (arr[i - 1]) {
// 把能被整除的数字标识出来
for (int j = i * i; j < n; j += i) {
arr[j - 1] = false;
}
}
}
for (int i = 2; i < n; i++) {
if (arr[i]) {
count += 1;
}
}
return count;
}
}
