素数筛
什么是素数筛
素数筛是一种可以快速求出一个整数范围 [1,a] 的素数的方法
为什么要用素数筛
有些人会说：
判断一个数是不是素数，我直接循环2到它的平方根
看看有没有它的因数不就好了吗
但你如果要筛出特别多素数TLE就老实了
而用素数筛就不同了，它可以求出近约1e7个素数还不会超时
（其实我没试过上线，不过1e7个还是轻轻松松）
非常实用
埃氏筛与欧拉筛
素数筛分为很多种
这里讲解最常见的两种——埃氏筛与欧拉筛
埃氏筛
思想
由于每个数必定可以分解质因数
所以要把每个素数的倍数全部排除掉
没有被排除的就是素数
步骤
准备一个标记数组vis，0（false）代表素数，1（true）代表合数
从2开始遍历，遇到一个没有被标记的i就范围内它的倍数标记即可
code:
#include <bits/stdc++.h>
using namespace std;
int n;
bool vis[100010];
int main(){
cin >> n;
for(int i = 2;i <= n;i++){
if(!vis[i]){
cout << i << " ";
for(int j = i * 2;j <= n;j += i){
vis[j] = 1;
}
}
}
return 0;
}
欧拉筛
思想
和埃氏筛类似，但是埃氏筛把素数所有倍数筛除，每个数可能被筛好几遍
欧拉筛则更为简单
但不仅素数要筛倍数
合数也要筛倍数
每个数只被它最小的质因数筛一遍
所以需要另外把素数记录下来以筛除合数
遇到一个数从最小素数开始筛
如果数组里的数有此素数的质因数
则停止筛除，否则跳到下一个素数继续筛
直到两数不成倍数关系或遍历到最后一个素数
步骤
不仅要准备vis数组
还要专门建立一个a数组存素数
从2开始，每遇到一个素数就存到a数组里
遇到一个数从最小素数a[1]开始筛
如果数组里的数有此素数的质因数
则停止筛除，否则跳到下一个素数继续筛
直到两数不成倍数关系或遍历到最后一个a[cnt]素数（cnt为素数个数）
code：
#include <bits/stdc++.h>
using namespace std;
int n, len;
bool vis[200010];
int a[100010];
int main(){
cin >> n;
for(int i = 2;i <= n;i++){
if(!vis[i]){
cout << i << " ";
a[++len] = i;
}
for(int j = 1;j <= len && i * a[j] <= n;j++){
vis[i * a[j]] = 1;
if(i % a[j] == 0) break;
}
}
return 0;
}
对比埃氏筛与欧拉筛
时空复杂度
埃氏筛时间复杂度最优情况 O(n log log n)，最坏情况 O(n log n)
空间复杂度 O(n)
由于线性的筛法
欧拉筛时间复杂度为 O(n)
空间复杂度约 O(n) （其中有素数原理，但估算为这个）
总结
| 算法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 埃氏筛 | O(nloglogn)O(nloglogn) | O(n)O(n) | 简单，但可能有重复标记 |
| 欧拉筛 | O(n)O(n) | O(n)O(n) | 线性效率，无重复标记 |
应用场景
- 埃氏筛：适合对效率要求不高或需要简单实现的场景
- 欧拉筛：适合大规模数据（如 n≥10^{7} ），需严格线性时间的情况