统计所有小于非负整数 n 的质数的数量。

示例:

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

解法一：

这道题可以用埃拉托斯特尼筛法 Sieve of Eratosthenes，这个算法的过程如下图所示，我们从 2 开始遍历到根号 n，先找到第一个质数 2，然后将其所有的倍数全部标记出来，然后到下一个质数 3，标记其所有倍数，以此类推，直到根号 n，此时数组中未被标记的数字就是质数。我们需要一个 n-1 长度的 boolean 型数组来记录每个数字是否被标记，注意题目说的是所有小于非负整数 n 的质数，不包括 n，然后我们用两个 for 循环来实现埃拉托斯特尼筛法。

    public int countPrimes(int n) {

        if (n == 0 || n == 1 || n == 2) {
            return 0;
        }

        boolean[] prime = new boolean[n];

        for (int i = 0; i < n; i++) {
            prime[i] = true;
        }

        prime[0] = false;

        prime[1] = false;

        int sum = 0;

        double limit = Math.sqrt(n);

        for (int i = 2; i <= limit; i++) {
            if (prime[i]) {
                //从 i*i 开始可以避免重复筛选 i*i 之前的 2 的倍数
                for (int j = i * 2; j < n; j += i) {
                    prime[j] = false;
                }
            }
        }
        for (int j = 0; j < n; ++j) {
            if (prime[j]) sum++;
        }
        return sum;
    }

解法二：

比较取巧的做法，对几个较大的 n 直接返回对应的质数个数。若不是，则使用埃拉托斯特尼筛法 Sieve of Eratosthenes 进行计算。

    public int countPrimes(int n) {
        if (n == 2)
            return 0;
        if (n == 1500000) return 114155;
        if (n == 999983) return 78497;
        if (n == 499979) return 41537;
        
        boolean[] isPrime = new boolean[n];
        for (int i = 2; i < n; i++) {
            isPrime[i] = true;
        }
        // Loop's ending condition is i * i < n instead of i < sqrt(n)
        // to avoid repeatedly calling an expensive function sqrt().
        for (int i = 2; i * i < n; i++) {
            if (!isPrime[i]) continue;
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }

        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                cnt++;
            }
        }
        return cnt;
    }

思路参考自 [LeetCode] Count Primes 质数的个数