- C++
埃氏筛 + 线性筛(欧拉筛)C++教程
- @ 2026-10-21 22:47:25
埃氏筛 + 线性筛(欧拉筛)C++教程
适合:GESP五级 重点:数学道理、优化原因、带详细注释、背诵思路、对比
目标:找出 1 ~ n 里面所有的质数 质数定义:大于1,只能被1和自己整除的整数
前置小知识(先讲数学)
质数:2、3、5、7、11、13…… 合数:4、6、8、9、10、12……(除了1和自己还有别的因数) 1 不是质数,也不是合数!
第一部分:埃氏筛(埃拉托斯特尼筛法)
✅ 数学依据(一定要给学生讲)
思路:
- 一开始我们先假设:所有数都是质数
- 找到一个质数 p,那么 p 的所有倍数:
2p,3p,4p...一定是合数,全部标记掉 - 标记完所有合数,剩下没被标记的,就是质数
举例子 n=10 一开始:[2,3,4,5,6,7,8,9,10]
- p=2(质数):划掉 4,6,8,10
- p=3(质数):划掉 6,9
- p=4:已经被划掉了,跳过
- p=5:5*2=10 超过范围,不用划 最后剩下 2,3,5,7 就是质数
✅ 优化1:循环到 sqrt(n) 就够了
道理:如果 n 有一个大于 的因数,那对应的另一个因数一定小于 ,早就被标记过了。 所以 i 不用跑到 n,跑到 就可以。
✅ 优化2:从 p*p 开始标记,不用从 2p
比如 p=5: 25=10,10早就被2标记了;35=15早就被3标记了。 比 p² 小的p的倍数,已经被更小的质数标记完了,直接从 p*p 开始筛,减少重复标记。
⚠️ 缺点(埃氏筛致命问题): 一个合数会被多次标记! 比如 12:会被2标记一次、又被3标记一次。重复干活,速度慢。 数字很大的时候,重复标记很多,效率变低。
✅ 埃氏筛完整代码,逐行注释
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
// is_prime数组:true代表是质数,false是合数
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false; // 0和1不是质数
// i从2到根号n
for (int i = 2; i * i <= n; i++)
{
// 如果i还没被标记,说明i是质数
if (is_prime[i])
{
// 从 i*i 开始,把i的倍数标记为合数,步长i
for (int j = i * i; j <= n; j += i)
{
is_prime[j] = false;
}
}
}
// 输出所有质数
cout << "1~" << n << "的质数:";
for (int i = 2; i <= n; i++)
{
if (is_prime[i])
{
cout << i << " ";
}
}
return 0;
}
📖 背诵思路(埃氏筛)
- 开布尔数组,初始全true;0、1改成false
- i循环:
i*i <= n - 如果is_prime[i]是true(i是质数)
- j从
i*i开始,j每次+i,标记is_prime[j]=false - 最后遍历输出没被标记的
第二部分:线性筛(欧拉筛,线筛)【GESP高频】
✅ 数学依据 + 为什么它更快(重点!)
埃氏筛的毛病:合数重复标记。 线性筛目标:保证 每一个合数,只被它的【最小质因子】标记一次! 每个数字只处理一遍,时间复杂度 (O(n)),所以叫线性筛。
核心规则:
我们维护一个质数数组 prime[],存已经找到的质数。
对于每一个数字 i:
- 如果i没被标记 → i是质数,加入prime数组
- 遍历已经找到的质数 prime[j]
- 把
i * prime[j]标记成合数 - 如果 i % prime[j] == 0,立刻break!>
break 这句是线筛灵魂! 道理:prime[j] 是i的最小质因子。如果继续往后乘 prime[j+1]
i * prime[j+1]的最小质因子其实是 prime[j],后面会重复标记,所以直接跳出循环,杜绝重复。 - 把
举例子 i=6,prime=[2,3,5] prime[j]=2:6%2==0 → break 不再去乘3、5,防止 6*3=18 被3标记(18最小质因子是2,应该留给i=9,prime[j]=2的时候标记)
✅ 线筛完整代码,逐行详细注释
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<bool> is_prime(n + 1, true); // 标记是否质数
vector<int> prime; // 存放找到的质数
is_prime[0] = is_prime[1] = false;
// i遍历2~n所有数
for (int i = 2; i <= n; i++)
{
// 如果i没有被标记,i是质数,放进prime数组
if (is_prime[i])
{
prime.push_back(i);
}
// 遍历已经找到的质数
for (int j = 0; j < prime.size(); j++)
{
int p = prime[j];
int num = i * p;
if (num > n) break; // 超过范围,不用标记
is_prime[num] = false;
// 灵魂判断:i能被p整除,立刻break
if (i % p == 0)
{
break;
}
}
}
// 输出质数
cout << "1~" << n << "的质数:";
for (int x : prime)
{
cout << x << " ";
}
return 0;
}
📖 背诵思路(线筛,分4句口诀,超好背)
- 两个数组:布尔标记is_prime,int数组prime存质数;0、1设false
- i从2循环到n;i是质数就push进prime
- 循环遍历prime里面的每个质数p
- 算 num = i * p,超n就break
- num标记合数
- 如果 i % p == 0 → break(核心!)
- 最后直接输出prime数组
✨ 一句话区分两个筛子 埃氏筛:找质数p,批量划p的倍数;会重复标记,简单好写,慢一点 线筛:保证每个合数只被最小质因子标记一次,没有重复,速度最快,GESP推荐优先写线筛
第三部分:对比总结(板书用)
| 筛法 | 时间 | 优点 | 缺点 | 核心 |
|---|---|---|---|---|
| 埃氏筛 | 逻辑简单,代码短,好理解 | 合数多次重复标记,大数据慢 | 质数划掉自己所有倍数 | |
| 线性筛 | 无重复标记,速度最快 | 逻辑稍微绕一点,要理解break | 每个合数只用最小质因子标记 |
第四部分:课堂小练习
- n=20,用埃氏筛手动模拟一遍,写出标记过程
- n=20,线筛,想一想为什么 i=4 的时候遇到 p=2 就要break?
第五部分:给学生的避坑提醒
- 数组大小一定要 n+1,因为我们要用到数字n
- vector 很省内存,筛大数优先用它
- 线筛的break千万不能丢,丢了就退化成普通筛,失去线性的优势
- ii 容易溢出!GESP如果n很大,优先用线筛,避免ii溢出问题
2 条评论
-
admin SU @ 2026-10-21 22:54:34已修改
我们慢慢拆开讲,大白话,小学生也能听懂:
先回顾埃氏筛为什么会重复标记
拿数字 12 举例: 12 = 2 × 6 12 = 3 × 4
- 当 i=2(质数)的时候:会把 4、6、8、12、14……全部标成合数
- 当 i=3(质数)的时候:会把 6、9、12、15……全部标成合数
👉 12 被标记了两次。 一个合数,只要它有多个质因子,就会被不同质数多次扫到,反复标记。 数字越大,重复次数越多,白白多干活,速度变慢。
核心思想:规定一条铁规矩
任何一个合数,只能由它最小的那个质因子负责标记它!
12 的质因子是 2 和 3,最小质因子是 2。 所以:12 只能交给 2 来标记,不许 3 再来标记 12。 同理: 18 = 2 × 9,最小质因子是 2,只能让2标记18,3不能标记18 15 = 3 × 5,最小质因子是3,只能让3标记15,5不能标记15
只要守住这条规矩:每个合数只会被标记一次,没有多余操作。
那代码里
if(i % p == 0) break;是怎么实现这条规矩的?for (int j = 0; j < prime.size(); j++) { int p = prime[j]; int num = i * p; if (num > n) break; is_prime[num] = false; if (i % p == 0) break; // 灵魂一句 }prime数组里面质数是从小到大排的:2,3,5,7,11…… p 从小到大拿出来。一旦
i % p == 0: 说明 p 是 i 的最小质因子!举例子:i=6,prime=[2,3,5]
- 第一个 p=2:
6 % 2 == 0✔ 立刻 break,不再去拿 p=3、p=5 继续乘。
为什么不能继续算
6 * 3 = 18? 18 = 6 × 3 但是 18 的最小质因子是 2,不是3! 如果现在用 6 × 3 标记18,就相当于让3去标记本该由2标记的合数,破坏规矩,以后就会出现重复标记。 18 正确标记时机:等 i=9 的时候,p=2,9*2=18,由最小质因子2标记。✅ 一句话: 只要 i 能被 p 整除,p 就是 i 的最小质因子;后面更大的质数乘出来的数,最小质因子还是 p,留给后面处理,现在直接停下。
为什么做到“每个合数只标记一次”之后,复杂度是 O(n)(线性)
总共有 2 ~ n,一共 n-1 个数。 每一个合数,刚好被标记 1 次;质数不被标记。 所有标记操作的总次数,不会超过 n。 工作量和 n 成正比,所以叫线性时间 O(n)。
对比: 埃氏筛:操作次数比 n 多很多,有大量重复,是 ,不是线性。
简短背诵版(给学生写笔记)
- 埃氏筛:同一个合数,会被好几个质数反复标记,重复干活,慢。
- 线性筛定下规则:合数只能由它最小的质因子标记,只标记一次。
if(i%p==0) break;的作用: p 是i的最小质因子,再往后更大质数相乘得到的数,最小质因子还是p,不能现在标记,立刻跳出循环。- 没有多余重复操作,总工作量和n成正比,时间O(n),叫线性筛。
要不要我拿 i=4、i=6、i=9 一步步手动模拟一遍完整线筛流程?跟着走一遍就彻底通透了。
手动模拟线性筛(n=20,一步步来)
初始:
is_prime[]全部先设为true;is_prime[0]=is_prime[1]=falseprime = [](空数组,用来存找到的质数) prime里面永远从小到大:2,3,5,7,11……规则再复习:
- 如果
is_prime[i]==true→ i是质数,放进prime数组 - 遍历prime里每一个质数p,算
num = i * p- num>20,停止内层循环
- is_prime[num] = false
- 如果
i % p == 0→ break内层循环!
i = 2 is_prime[2]=true → 2是质数,prime变成
[2]内层循环遍历prime: p=2,num=2*2=4 ≤20 is_prime[4]=false 判断:2%2 ==0 ✅ → break内层循环现在标记了:4
i = 3 is_prime[3]=true → 3是质数,prime变成
[2,3]内层循环: p=2,num=32=6 ≤20,is_prime[6]=false 判断:3%2≠0,不break,继续 p=3,num=33=9 ≤20,is_prime[9]=false 判断:3%3==0 ✅ → break现在标记新增:6、9
i = 4 is_prime[4]=false,不是质数,不加入prime,prime还是
[2,3]内层循环: p=2,num=42=8 ≤20,is_prime[8]=false 判断:4%2 ==0 ✅ → break!不拿p=3继续算 43=12 👉 重点:12的最小质因子是2,不该在这里用4×3标记,留给后面处理新增标记:8
i = 5 is_prime[5]=true → 5是质数,prime变成
[2,3,5]内层循环: p=2,num=52=10,is_prime[10]=false,5%2≠0 p=3,num=53=15,is_prime[15]=false,5%3≠0 p=5,num=5*5=25 >20 → break新增标记:10、15
i = 6 is_prime[6]=false,不进prime,prime
[2,3,5]内层循环: p=2,num=62=12 ≤20,is_prime[12]=false 判断:6%2 ==0 ✅ → break!不再算63=18 👉 18最小质因子是2,不能现在标记新增标记:12
i = 7 is_prime[7]=true → 7是质数,prime变成
[2,3,5,7]内层循环: p=2 → num=14,标记14,7%2≠0 p=3 → num=21>20,停止内层新增标记:14
i = 8 is_prime[8]=false 内层循环: p=2,num=8*2=16,标记16 8%2==0 → break
新增标记:16
i = 9 is_prime[9]=false 内层循环: p=2,num=92=18,标记18 9%2≠0,继续 p=3,num=93=27>20,停止
✅ 这里终于标记了18! 18 = 9 × 2,最小质因子是2,符合规矩! 之前i=6的时候不让标记18,就是等这一刻 新增标记:18
i = 10 is_prime[10]=false 内层循环: p=2,num=10*2=20,标记20 10%2==0 → break
新增标记:20
i=11 ~ 20: i=11:质数,加入prime;p=2 → 22>20,内层直接结束,无标记 i=12:合数;p=2 → 24>20,无标记 i=13:质数;p=2→26>20 i=14:合数;p=2→28>20 i=15:合数;p=2→30>20 i=16:合数;p=2→32>20 i=17:质数;p=2→34>20 i=18:合数;p=2→36>20 i=19:质数;p=2→38>20 i=20:合数;p=2→40>20
✅ 全部标记过的合数汇总: 4,6,8,9,10,12,14,15,16,18,20 每一个合数,只被标记了一次! 我们检查18:只在i=9,p=2的时候标记,仅此一次。
✅ 最后prime数组里面的质数:
[2,3,5,7,11,13,17,19]提炼这个模拟里面最关键的两处
- i=4,p=2,4%2==0,break,不计算4*3=12 12交给i=6,p=2的时候标记(最小质因子2)
- i=6,p=2,6%2==0,break,不计算6*3=18 18交给i=9,p=2的时候标记(最小质因子2)
只要触发
i%p==0就break,就是为了守住:合数只能由最小质因子标记课堂一句话总结
只要break写对,没有一个合数会被重复打上标记,总操作次数和n差不多,所以叫线性筛O(n)。
练习1(课堂手写题)
题目:n=15,用线性筛手动模拟,按步骤填空 初始:
is_prime[0]=is_prime[1]=false,其余初始true;prime = []规则复习:
- 如果
is_prime[i]==true→ i是质数,push_back进prime - 依次取 prime[j]=p,
num = i * p- num>15,停止内层循环
- is_prime[num]=false
- 如果
i % p == 0→ break内层循环!
请一步步填写: i = 2 is_prime[2] = true → prime = [____] p=2,num=4,标记4为合数;2%2==0 → break 本次标记合数:________
i = 3 is_prime[3] = true → prime = [,] p=2,num=6,标记6;3%2≠0,继续 p=3,num=9,标记9;3%3==0 → break 本次标记合数:________
i = 4 is_prime[4]=false p=2,num=8,标记8;4%2==0 → break 本次标记合数:________
i = 5 is_prime[5]=true → prime = [,,] p=2,num=10,标记10;5%2≠0 p=3,num=15,标记15;5%3≠0 p=5,num=25>15,停止 本次标记合数:______
i = 6 is_prime[6]=false p=2,num=12,标记12;6%2==0 → break 本次标记合数:________
i=7:质数,加入prime,p=2 → 14,标记14;7%2≠0,p=3→21>15结束 本次标记合数:14
i=8~15:i*2全部大于15,不再产生新标记
👉 问题:
- 最后prime里面存放的质数是哪些?
- 合数15是在哪一轮、i等于几、p等于几的时候被标记的?
- 思考:i=6的时候,为什么break,不能算 6*3=18?
参考答案(老师版)
i=2:prime=[2],标记:4 i=3:prime=[2,3],标记:6、9 i=4:prime不变,标记:8 i=5:prime=[2,3,5],标记:10、15 i=6:prime不变,标记:12 i=7:prime=[2,3,5,7],标记:14
- 最终质数:2,3,5,7,11,13
- 15:i=5,p=3
- 18超过n=15,这题里不会出现;核心道理:如果n更大,18最小质因子是2,不能用6×3标记,防止重复标记
-
@ 2026-10-21 22:48:20
更新后完整试卷(空白学生版)
筛法专项课堂小测(埃氏筛、线性筛) 满分:40分,课堂20分钟完成
一、填空题(每空2分,共16分)
- 质数定义:大于1,只能被______和______整除的正整数;数字______既不是质数也不是合数。
- 埃氏筛的核心思想:找到一个质数p,把p所有的______标记为合数。
- 埃氏筛优化:j不从 2*p 开始,而是从 ______ 开始标记,原因是:比这个数小的p的倍数,已经被更小的质数标记过了。
- 线性筛(欧拉筛)的目标:每一个合数,只被它的________标记一次,保证没有重复标记。
- 线筛里面灵魂一句:if(i % p == 0) break; 如果删掉这句,线筛就退化成普通筛,会出现________标记合数的问题。
- 模数n=30,筛的时候数组要开到______,才能存到数字30。
二、选择题(每题3分,共12分)
- 下面哪一个是质数?() A. 9 B. 13 C. 15 D. 21
- 埃氏筛 i 的循环条件写成 i*i <= n,主要目的是() A. 代码更好看 B. 减少循环次数,不用循环到n C. 防止输出错误 D. 让程序变成线性时间
- 关于埃氏筛和线性筛说法正确的是() A. 埃氏筛时间复杂度O(n) B. 线性筛会多次标记同一个合数 C. 线性筛依靠最小质因子筛数 D. 埃氏筛不能筛100以内质数
- 在线性筛中,prime数组作用是() A. 标记数字是不是质数 B. 存放已经找到的质数 C. 存放合数 D. 记录循环次数
三、读代码简答题(每题4分,共8分)
- 模拟埃氏筛:n=12
一开始:0、1标记为false,2
12默认true i=2,是质数,从4开始标记4,6,8,10,12为合数; i=3,是质数,从9开始标记9、12为合数; i=4:is_prime[4]是false,跳过; 问:112里面最后剩下哪些质数? - 线筛思考题:i=6,质数列表prime={2,3,5} 第一轮p=2,num=62=12,标记12为合数; 然后判断 6 % 2 == 0,触发break,不再拿6去乘3、5。 请问:为什么这里必须break,不能继续算 63=18?
四、编程题(4分) 编写线性筛(欧拉筛)C++代码,输入n,输出1~n之间全部质数。 要求:使用vector,注释可以简写。
参考答案版
一、填空
- 1,它本身,1
- 倍数
- p*p
- 最小质因子
- 重复
- 31
二、选择 1.B 2.B 3.C 4.B
三、简答
- 2、3、5、7、11
- 18的最小质因子是2。如果现在用i=6、p=3标记18,属于重复标记;18应当在后面i=9,p=2的时候,由最小质因子2标记。break用来杜绝重复标记,保证线性。
四、编程参考代码
#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<bool> is_prime(n+1,true); vector<int> prime; is_prime[0]=is_prime[1]=false; for(int i=2;i<=n;i++) { if(is_prime[i]) prime.push_back(i); for(int j=0;j<prime.size();j++) { int p=prime[j]; int num=i*p; if(num>n) break; is_prime[num]=false; if(i%p==0) break; } } for(int x:prime) cout << x << " "; return 0; }
- 1