[LeetCode]204. 计数质数（java实现）筛质数模板题、线性筛法

[LeetCode]204. 计数质数（java实现）筛质数模板题、线性筛法

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

1. 题目

2. 读题（需要重点注意的东西）

思路（筛质数——线性筛法）：

因此时间复杂度是O(n)的

线性筛法的证明详见[AcWing]868. 筛质数（C++实现）线性筛模板题

3. 解法

---------------------------------------------------解法---------------------------------------------------

class Solution {
    public int countPrimes(int n) {
        boolean[] st = new boolean[n];
        List<Integer> primes = new ArrayList<>();
        for(int i = 2;i < n;i++){ // 注意1既不是质数也不是合数
            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;  // break保证了只筛一次
            }
        }
        return primes.size();
    }
}

---

可能存在的问题：

4. 可能有帮助的前置习题

• [AcWing]868. 筛质数（C++实现）线性筛模板题

5. 所用到的数据结构与算法思想

• 线性筛

6. 总结

线性筛筛质数的模板题，背下来！