Curiosity

如何快速生成质数候选

解释筛法通过预先标记倍数来实现批量淘汰的机制，并说明它在候选质数生成中相对于试除法的效率优势。

Before you enter

A complete interactive classroom, not just a preview.

Start when you are ready to enter this Stage's 8 scenes and explore, respond, and learn as you go.

Scenes

16 min

Estimated

Content language: zh-CN

Created by

MathClue

Start this Stage

Remix into your version

Sign-in may be required to play

What happens inside

01一个看似朴素的问题slide
Question
提出驱动问题：在 1 到 N 的范围里，怎样才能尽快筛出所有质数候选？
- 驱动问题：筛法为何比试除法更快？
- 展示 N=100 时逐个试除的工作量
- 引出'批量淘汰'的直觉
02先猜一猜quiz
Prediction
在揭示筛法机制之前，让学习者先做出直觉判断。
- 让学习者承诺一个初始假设
- 为后续对比制造认知落差
03埃拉托色尼筛法可视化interactive
Evidence
可交互的筛法演示：学习者选择 N 的大小，逐步划掉每个素数的倍数，直观看到'批量淘汰'的过程。
- 动态演示筛掉 2、3、5、7 的倍数
- 对比剩余数字比例随 N 变化
- 观察筛法只对每个素数操作一次
04为什么筛法更快slide
Explanation
解释筛法的核心机制：合数必然有不超过 √N 的最小素因子，因此只需用小素数批量划掉倍数即可。
- 合数 = 小素数 × 某个整数
- 只需对素数 p 操作一次即可划掉 p², p·(p+1), …
- 时间复杂度从 O(N√N) 降到约 O(N log log N)
05实测耗时对比interactive
Evidence
让学习者调整 N 的大小，同时启动'试除法'和'筛法'两个计数器，实时观察运行步数差异。
- 小 N 时差距不明显
- N 增大时试除法步数爆炸，筛法线性增长
- 强化'批量筛选'的复杂度优势
06筛法的代价与适用边界slide
Boundary
诚实指出筛法的局限：内存占用 O(N) 决定了它不适合超大区间，并引出分段筛与概率素性测试的过渡。
- 空间复杂度 O(N) 是瓶颈
- 分段筛（segmented sieve）缓解内存压力
- 极大候选场景下转向 Miller-Rabin 等概率测试
07迁移：加密系统里的候选质数interactive
Transfer
把筛法思想迁移到 RSA 候选生成场景：学习者尝试用筛法从一个 1024 位候选池中预筛，再交给概率测试。
- 先批量剔除明显合数
- 再对少量候选做高精度测试
- 体现'筛法 + 素性测试'的标准流水线
08回到驱动问题slide
Resolution
直接回答开篇问题，总结筛法为何能更快生成质数候选，并给出可操作的要点。
- 核心思想：利用合数的结构性一次划掉一批
- 时间从 O(N√N) 降到 O(N log log N)
- 实际系统通常把筛法作为'快速预筛'环节