🌟《素数王国的两种超级筛子》
故事前言：
1、在数字王国里，国王需要一份素数名单。
（1）比如：
1 ~ 30 之间的所有素数（2）答案应该是：
2 3 5 7 11 13 17 19 23 29（3）问题来了：
如果数字很大，比如：
1 ~ 1,000,000（4）一个一个判断素数就会非常慢。
2、于是王国发明了两种神器：
1️⃣埃氏筛（Eratosthenes Sieve）
2️⃣线性筛（Euler Sieve）
今天我们就来学习这两个神器。
第一部分：埃氏筛法（筛沙子）
🌾故事：筛沙子找金子
小C来到一条河边。
河里有很多沙子（合数）和金子（素数）。
工人拿来一个大筛子：
每发现一个素数，就把它的倍数全部筛掉！
这样剩下的就都是素数。
一、筛法思想
1、假设我们要找
1 ~ 30 的素数2、先把所有数写出来：
2 3 4 5 6 7 8 9 10 11 ... 303、我们准备一个数组：
isPrime[i]4、表示：
i 是否是素数5、开始全部设为：
true二、开始筛
1、第一步：2 是素数
（1）因为 2 没被划掉。
于是：
把2 的倍数全部划掉
4 6 8 10 12 14 16 18 20 22 24 26 28 30（2）剩下：
2 3 5 7 9 11 13 15 17 19 21 23 25 27 292、第二步：3 是素数
因为 3 没被划掉。
划掉：
6 9 12 15 18 21 24 27 303、第三步：5 是素数
划掉：
10 15 20 25 30最后剩下：
2 3 5 7 11 13 17 19 23 29这些就是素数。
三、为什么只筛到 √n？
（1）比如
n = 100（2）如果一个数是合数：
a × b = n（3）那么一定有：
一个 ≤ √n 一个 ≥ √n（4）所以只要筛到：
i * i <= n就可以了。
四、埃氏筛 C++模板
#include <iostream> using namespace std; const int N = 1000000; bool isPrime[N]; int main() { int n; cin >> n; for(int i=2;i<=n;i++) isPrime[i]=true; for(int i=2;i*i<=n;i++) { if(isPrime[i]) { for(int j=i*i;j<=n;j+=i) isPrime[j]=false; } } for(int i=2;i<=n;i++) if(isPrime[i]) cout<<i<<" "; }五、为什么从 i*i 开始？
（1）很多同学会问：
为什么不是：
2*i（2）例如：
i = 5（3）5 的倍数：
10 15 20 25（4）向前看一下：
10 已经被 2 删过 15 已经被 3 删过 20 已经被 2 删过（5）所以：
从 25 开始可以节省时间
也就是：
i * i六、埃氏筛时间复杂度
大约是：
O(n log log n)已经非常快了。
第二部分：线性筛
我们见到了一个更厉害的科学家，他叫欧拉。
他说：
我有一种方法，可以让每个合数只被删一次！
这就是：
线性筛（Euler筛）
一、线性筛思想
核心思想：
每个合数 = 最小质因数 × 另一个数只用最小质因数来筛掉它。
这样就不会重复删除。
二、例子（还是1~30）
我们一边走一边记录素数表
1、i = 2
2 是素数
加入素数表：
prime = {2}筛：
2×2 = 42、i = 3
3 是素数
prime = {2,3}筛：
3×2 = 6 3×3 = 93、i = 4
4 已经被删
不是素数
但继续筛：
4×2 = 84、i = 5
5 是素数
prime = {2,3,5}筛：
5×2 = 10 5×3 = 15 5×5 = 255、就这样一直继续。
每个合数只被最小质因数筛一次。
三、线性筛 C++模板
#include <iostream> using namespace std; const int N = 1000000; int prime[N]; bool vis[N]; int main() { int n; cin >> n; int cnt = 0; for(int i=2;i<=n;i++) { if(!vis[i]) prime[cnt++] = i; for(int j=0;j<cnt && i*prime[j]<=n;j++) { vis[i*prime[j]] = true; if(i%prime[j]==0) break; } } for(int i=0;i<cnt;i++) cout<<prime[i]<<" "; }四、为什么要 break？
1、关键一句：
if(i % prime[j] == 0) break;2、意思是：
如果：
prime[j]已经是i 的最小质因数
3、那：
i × 更大的质数就不是最小质因数分解了。
所以必须停止。
4、这样保证：
每个合数只被筛一次
五、时间复杂度
线性筛：
O(n)是真正的线性时间
六、两种筛法对比
| 方法 | 原理 | 复杂度 |
|---|---|---|
| 埃氏筛 | 删除倍数 | O(n log log n) |
| 线性筛 | 最小质因数 | O(n) |
七、理解区别
1、埃氏筛
（1）特点：
一个合数会被删除很多次（2）例如
30（3）会被：
2删 3删 5删2、线性筛
（1）特点：
每个合数只删除一次（2）例如：
30 = 2 × 15只由2删除。
八、什么时候用哪种筛法？
1、小数据
n ≤ 10^6用：
埃氏筛
简单好写。
2、大数据
n ≤ 10^7 或更大用：
线性筛
更快。
九、最重要的理解总结
（1）埃氏筛
思想：
发现素数 → 删除倍数（2）线性筛
思想：
用最小质因数删除合数十、一句话记忆
（1）埃氏筛：
素数 × 所有倍数（2）线性筛：
每个合数只筛一次
