素数筛选中的两种经典方法——埃拉托色尼筛法（埃氏筛）和线性筛法-野牛程序员教少儿编程

素数筛选中的两种经典方法——埃拉托色尼筛法（埃氏筛）和线性筛法-野牛程序员教少儿编程

素数大揭秘：埃氏筛 & 线性筛的魔法课堂

—— 青少年信息学竞赛入门系列 · 第讲

🧠 什么是素数？

在数学的王国里，有一类数特别“孤傲”——它们除了 1 和自己，谁也不认识。

比如：

2、3、5、7、11、13……这些都是素数（Prime Number）

而 4=2×2，6=2×3，9=3×3……这些叫合数（Composite Number）

🧩 小测试：

以下哪些是素数？

17，21，23，27，29

答案： 17, 23, 29 是素数； 21, 27 是合数

如何快速找出素数？

从 1 到 10 万中找素数，数一个算一个？太慢！

于是，数学家们发明了两种“批量筛选”的绝招：

第一招：埃拉托色尼筛法

（英文名：Eratosthenes Sieve）

思想：

每当遇到一个素数，就把它的倍数全部划掉，留下的就是素数！

举个例子（1~30）：

2 是素数 划掉 4,6,8,...

3 是素数 划掉 6,9,12,...

5 是素数 划掉 10,15,20,...

最后剩下的就是：2, 3, 5, 7, 11, 13, 17, 19, 23, 29

方法一：埃拉托色尼筛法（Eratosthenes）

第二招：线性筛法（欧拉筛）

思想：

每个合数，只被它的最小质因子标记一次，绝不重复！

🧠 什么是“最小质因子”？

比如：

6 = 2×3 最小质因子是 2

15 = 3×5 最小质因子是 3

77 = 7×11 最小质因子是 7

方法二：线性筛法（欧拉筛）

亮点：

不重复标记，效率更高

时间复杂度是 $O(n)，适合数据量超大的场景

🧮 对比总结表

野牛程序员教少儿编程与信息学奥赛

宜宾市野牛网络科技有限公司专业微信小程序开发、网站建设、软件开发等