本文主要是介绍埃氏筛-找素数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 1、描述
- 2、关键字
- 3、思路
- 4、notes
- 5、复杂度
- 6、code
1、描述
统计所有小于非负整数 n 的质数的数量。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-primes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2、关键字
素数
3、思路
指数更新
4、notes
先初始化一个标记数组，然后根据标记数组是否是之前素数的倍数，来判断是否是素数，
一些边界条件：long long i * i
5、复杂度
时间：O(nloglogn)
空间：O（N）
6、code
class Solution {
public:int countPrimes(int n) {vector<int>isPrime(n,1);vector<int>res;for(int i = 2; i < n; i++){ // 这里：i <= n;也会错 if(isPrime[i]){res.push_back(i);isPrime[i] = 0;if((long long) i * i < n){ // 这里不写会越界，如果写成if((long long) (i * i) < n)也是越界for(int j = i*i; j <n; j += i){isPrime[j] = 0;}}}}return res.size();;}
};
这篇关于埃氏筛-找素数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
