如何高效筛素数？让我们来看看
题目：生成一个1到n范围内的质数数组
菜鸟这样做（枚举法）
从1枚举到n，判断是素数就存入数组
下面是判断方法
菜鸟：
从2枚举到n-1，如果有能整除该数的，该数就是质数。
进化版菜鸟：
菜鸟进化了，从2枚举到$\sqrt n$
高手版
埃氏筛
这样筛掉后每次下一位没被筛掉的数就都是质数
bool numlist[100000];
//0代表质数，1代表非质数
int prime[100000], count;
void work(int n){
for(int i=2; i<=n; i++){
if(numlist[i]==0){ //如果是质数
prime[++count] = i ; //就先存入
for(int j=i; i*j<=n; j++) numlist[i*j] = 1; //然后将其平方后的所有倍数筛掉
}
}
return;
}
但是这钟筛法还不是最优，因为p的倍数会重复，所以有些数会被重复筛掉。
那么就引出了我们的最终筛法。
欧拉筛
这个筛法避免了重复筛，思路就是：每个合数只会被其最大非自身因数筛除
多说无益，先上代码：
bool numlist[100000];
//0代表质数，1代表非质数
int prime[100000], count;
void work(int n){
for (int i = 2; i <= n; i++) {
if (numlist[i]==0) ans[++count] = i;//是质数就先存入数组
for (int j = 1; j <= count && i*prime[j] <= n; j++) {
numlist[prime[j] * i] = 1; //每次让i乘已放入的质数，然后标记非质数
if (i % prime[j] == 0) break;//但是如果i可以被该数整除就停止（关键）
}
}
现在我们再来分析下。
从表可以看出，我们会筛掉每个质数p的平方之后的p的倍数，但是如果i是p的倍数，那就说明它们的乘积那个合数的最大非自身因数不是i，所以不筛。
| i 的值 | 质数表 | 筛去的数 |
|---|---|---|
| 2 | 2 | 4 |
| 3 | 2, 3 | 6, 9 |
| 4 | 2, 3 | 8 |
| 5 | 2, 3, 5 | 10, 15, 25 |
| 6 | 2, 3, 5 | 12 |
| 7 | 2, 3, 5, 7 | 14, 21, 28, 35 |
| ⋯ | ⋯ | ⋯ |