统计所有小于非负整数 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;
    }
}