算法入门｜埃拉托斯特尼筛法，一张表筛出 1~120 所有质数
简介
课堂上用表格直观演示埃拉托斯特尼筛法，一次性筛选 1~120 全部素数。本文结合 PPT 表格图解拆解筛法原理、完整执行步骤、优缺点，附上可直接运行的 Java 代码，适合算法入门、课堂作业复习。
一、课堂演示图说明
屏幕表格范围：数字 2 ~ 120，表格通过标红 / 涂色标记非素数（合数），未被涂色的灰色数字就是质数（Prime numbers）。
核心规则：从最小素数 2 开始，不断标记当前素数的所有倍数，全部标记完成后，剩下未标记数字就是 1~120 范围内全部素数。
二、什么是埃拉托斯特尼筛法（埃氏筛）
- 基础概念
质数（素数）：大于 1，只能被 1 和自身整除的整数。
埃氏筛（Sieve of Eratosthenes）是高效批量查找区间内所有素数的经典算法，不用逐个数字试除，通过倍数批量排除合数，大幅降低时间复杂度。 - 核心思想
数字 2 是最小、唯一的偶素数；
把 2 的所有倍数全部标记为合数（4、6、8、10…120）；
找到下一个未标记数字 3，标记 3 所有倍数（6、9、12…120）；
继续取下一个未标记数字 5，标记 5 所有倍数；
循环到数字√上限（本案例上限 120，只需循环到 11），剩余未标记数字全部是素数。
三、结合课堂表格，分步还原筛选 1~120 全过程
步骤 1：初始化
列出 2~120 全部数字，默认全部判定为素数（表格浅灰色底色）。
数字 1 直接丢弃，1 既不是素数也不是合数。
步骤 2：处理素数 2
2 是素数，将表格里所有 2 的倍数标红：
4,6,8,10,12…120 全部标记为合数。
表格中所有偶数列数字被涂色，偶数除 2 外都不是素数。
步骤 3：处理下一个未标记数字 3
3 是素数，标记 3 全部倍数：
6,9,12,15,18…120
6、12 等已经被 2 标记，重复标记不影响结果。
步骤 4：下一个未标记数字 5
标记 5 倍数：10、15、20…120，表格末尾整十数字全部变红。
步骤 5：持续循环到√120≈11
依次处理 7、11：
7 的倍数：14、21、28…119
11 的倍数：22、33、44…121（超出 120 截止）
步骤 6：筛选结束
所有被涂色标红的是合数；表格中保持浅灰色、无填充的数字，就是 2~120 全部素数。
图右侧标注Prime numbers 2，代表 2 是第一个基础素数。
四、埃氏筛优缺点分析
优点
批量筛选，时间复杂度 O (n log log n)，远优于逐个试除暴力解法；
逻辑直观，表格可视化后极易理解，课堂教学首选；
只需一次遍历就能得到区间全部素数，适合打素数表、预处理。
缺点
需要开辟长度为 n 的布尔数组存储标记，有额外空间开销；
筛选超大数字区间时内存占用会快速上升；
会重复标记同一个合数（如 6 同时是 2 和 3 倍数），存在少量重复操作。
五、Java 完整代码实现（筛出 1~120 素数，对应课堂案例）
publicclassEratosthenesSieve{publicstaticvoidmain(String[]args){// 上限和课堂表格一致：120intmax=120;// 布尔数组标记是否为素数，默认true代表初始判定为素数boolean[]isPrime=newboolean[max+1];// 初始化：2~120全部设为素数for(inti=2;i<=max;i++){isPrime[i]=true;}// 埃氏筛核心循环，循环到平方根即可intsqrtMax=(int)Math.sqrt(max);for(inti=2;i<=sqrtMax;i++){// 如果当前数字是素数，批量标记它的所有倍数if(isPrime[i]){// 从i*i开始标记，更小倍数已经被更小素数标记过for(intj=i*i;j<=max;j+=i){isPrime[j]=false;}}}// 输出1~120所有素数，和课堂表格结果对照System.out.println("1~120之间所有素数：");for(inti=2;i<=max;i++){if(isPrime[i]){System.out.print(i+" ");}}}}六、学习总结
课堂上的数字表格把抽象的埃氏筛算法直观可视化，让我看懂批量排除合数的核心逻辑。对比暴力逐个试除判断素数，埃氏筛通过倍数批量标记极大提升了运算效率，适合一次性获取区间全部素数。
同时我也理解了算法取舍：埃氏筛以少量内存空间换取更低时间复杂度，不同业务场景要根据数据规模选择合适素数查找方案。本次演示案例上限 120 规模小，表格形式清晰易懂，是入门数论算法很好的练习案例。