题目描述

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

样例

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

算法分析

1、用线性筛法把[0, n)的质数全部筛出来即可
2、注意：筛[0,n]区间内的质数和筛[0,n)区间内的质数的区别在于这行代码for (int j = 0; i * primes.get(j) < n; j++) ，若i * primes.get(j) <= n，则就筛[0,n]的所有质数,也可以写成primes.get(j) <= n / i;i * primes.get(j) < n，则筛[0,n)的所有质数

第一次这么踩坑，记录一下

时间复杂度 $O(n)$

Java 代码

class Solution {
    public int countPrimes(int n) {
        boolean[] st = new boolean[n];
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i < n; i++) {
            if (!st[i]) primes.add(i);
            for (int j = 0; i * primes.get(j) < n; j++) {
                st[i * primes.get(j)] = true;
                if (i % primes.get(j) == 0) break;
            }
        }
        return primes.size();
    }
}