质数(java实现)筛质数模板题、线性筛法"/>
[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. 总结
线性筛筛质数的模板题,背下来!
更多推荐
[LeetCode]204. 计数质数(java实现)筛质数模板题、线性筛法
发布评论