1.题目

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

示例：

  1. 输入：n = 10
  2. 输出：4
  3. 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
  5. 输入：n = 0
  6. 输出：0
  8. 输入：n = 1
  9. 输出：0

提示：

  • 0 <= n <= 5 * 106

2.思路

我们首先要知道什么是质数：质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数。

没有什么思路，先写个答案上来，再慢慢想吧

    public int countPrimes(int n) {
        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i] == 1) {
                ans += 1;
                if ((long) i * i < n) {
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }

官方思路：
1.png