🌟《素数王国的两种超级筛子》
故事前言：
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 … 30
3、我们准备一个数组：
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 29
2、第二步：3 是素数
因为 3 没被划掉。
划掉：
6 9 12 15 18 21 24 27 30
3、第三步：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 = 4
2、i = 3
3 是素数
prime = {2,3}
筛：
3×2 = 6
3×3 = 9
3、i = 4
4 已经被删
不是素数
但继续筛：
4×2 = 8
4、i = 5
5 是素数
prime = {2,3,5}
筛：
5×2 = 10
5×3 = 15
5×5 = 25
5、就这样一直继续。
每个合数只被 最小质因数筛一次。
三、线性筛 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）线性筛：
每个合数只筛一次
