目录
概述
1.埃氏筛
思路
复杂度
Code
2.欧拉筛（线性筛）
思路
复杂度
Code
总结
概述
上一节我们介绍了对判断一个数是否为质数的方法：「数学::质数」试除法 / Luogu P5736（C++）
那如果我们期望输出一个范围内的所有质数，使用试除法的时间复杂度是n√n，怎么办呢？
LeetCode 204：
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
1.埃氏筛
思路
质数的倍数一定不是质数；反之，一个数不是任何比它小的质数的倍数，它一定是质数。
定义bool not_prim数组，not_prim[i]值为真，表示i不是质数；值为假，表示i是质数。
从i=2遍历到n:
如果not_prim[i]=false，表示它不是之前的任何一个数的倍数，也就是没有被筛掉，则它是质数，加入答案，再枚举它的倍数，将之筛掉。
如果not_prim[i]=true，表示它不是质数，直接枚举他的倍数，将之筛掉。
在枚举i的倍数依次筛掉时，我们可以直接从i^2开始枚举，因为i到i^2之间的数已经被i前面的数筛过了。下附证明
证明：
设有质数b，则kb为其整数倍(k=2,3...b-1)，即: 2b<=kb<=(b-1)*b。
注意到，k可表示为小于b的某一质数a的t倍。即：k=at(t>=1)。
则kb=atb，令tb=u，有kb=ua，其中u为a的某一倍数，因此筛a的倍数时已经筛掉了kb。
*注意*：我们只计算n以内的质数，因此ua=kb<n。
复杂度
时间复杂度: O(nlog(logn))
空间复杂度: O(n)
时间复杂度证明详见OI Wikihttps://oi-wiki.org/math/number-theory/sieve/，此处略去不表
Code
const int N=5e6+1;
class Solution {bool not_prim[N]={1,1,0};vector<int>prim;
public:int countPrimes(int n) {for(int i=2;i<n;i++){if(!not_prim[i])prim.push_back(i);for(long long j=1LL*i*i;j<n;j+=i)//1ll是为了防爆intnot_prim[j]=true;}return prim.size();}
};2.欧拉筛（线性筛）
思路
埃氏筛进行了很多次无用的筛数，比如说枚举2的倍数后已经不必再枚举4的倍数了。
欧拉想了一个方法：限制每个数的枚举上限。
比如说限制2的枚举倍数，使得4的倍数不会被2全部枚举一遍，这样每个数都只枚举几次，使得时间复杂度达到线性级别，故又称线性筛。
bool not_prim数组和筛倍数的策略仍然保持不变，但是我们多了两条原则：
①：i不仅用于枚举[2,n)的所有数是否为质数，也作为倍数用来筛数。
这是指双层for循环，外层i枚举所有数，内层j枚举所有已获得的质数，令not_prim[prim[j]*i]=true;
*注意*：埃氏筛中，i枚举所有数，j枚举倍数；欧拉筛中，i枚举所有数，同时作为倍数，j则枚举已知质数。
②：i%prim[j]==0时停止继续枚举j，保证每个合数都被他的最小质因子筛掉。
我们重点讲一下这个原则：
考虑：
i会枚举[2,n)之间的所有数，那i自然就可以表示倍数k，那么对于每个i都枚举已知的prim[j]进行筛倍数是合理又合法的。
遍历到i时，已经知晓了[2,i]之间的所有数是否是质数。同时可以确定的是，prim[j]必定是小于等于i的质数，且其中元素升序排序。
在我们筛掉i*prim[j]=x后，如果i%prim[j]==0，即i=k*prim[j]，就不必再筛i*prim[j+1]=y了，因为i*prim[j+1]可以被分解为k*prim[j]*prim[j+1]，即k*prim[j+1]*prim[j]，其中k*prim[j+1]将是后续的某个i值。
如i=6是prime[1]=3的倍数，我们在筛完i*prim[1]=18之后，不必再筛i*prim[2]=30了，因为当i=10时，30会被i*prim[1]筛掉。
j 0 1 2 3
prime[j] 2 3 5 7 复杂度
时间复杂度: O(n)
空间复杂度: O(n)
Code
const int N=5e6+1;
class Solution {bool not_prim[N]={0};vector<int>prim;
public:int countPrimes(int n) {for(int i=2;i<n;i++){if(!not_prim[i])prim.push_back(i);for(int j=0;prim[j]*i<n;j++){not_prim[prim[j]*i]=true;if(!(i%prim[j]))break;}}return prim.size();}
};*注意*：使用vector存储所有质数是为了减小空间复杂度，如果你希望达到欧拉筛的最优性能，可以开一个巨大的定长数组存储质数。
总结
埃氏筛和欧拉筛是两种几乎跑在线性时间的质数算法，他们在处理大量数据时的性能极其优异，我们尤其希望你理解了欧拉筛的两条原则，这有助于培养线性递推的能力。
