Python 赋能数学学习 8:一文读懂埃氏筛质数法:数学原理与算法模拟实现

1、新问题：如何快速找出 1 到 n 之间的所有质数？

在上一篇中，我们学习了如何判断“一个数是不是质数”。

如果只判断一个数，这样做很好用。

但如果我们想一次性找出 1 到 100、1 到 1000 里的全部质数，再一个个去判断就会比较慢。

这时可以用一种非常经典的方法：埃拉托斯特尼筛法（简称“埃氏筛”）。

它的想法很像“筛沙子”：

• 先把 2 到 n 的数都摆出来
• 从2开始,取没有处理过且没有划掉的数 p（初始时 p=2）
• 把它的倍数全部划掉（因为倍数一定是合数）
• 重复这个过程，直到筛到  就停了

举例：如果要找出 2 到 30 的质数：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

1.1 第一轮（p=2）：

划掉 4、6、8、10、12、14、16、18、20、22、24、26、28、30

数列变成了：

1.2 第二轮 （p=3）：

取队列中的下一个没被划掉的数 3 (p=3)：

划掉 6、9、12、15、18、21、24、27、30（其中 6、12、18、24、30 已经被划掉了）

数列变成了：

1.3 第三轮（p=5）：

取队列中的下一个没被划掉的数 5 (p=5)：

划掉 10、15、20、25、30（其中 10、15、20、30 已经被划掉了） 数列变成了：

23456789101112131415161718192021222324252627282930

1.4 最后一轮（p=7）：

取队列中的下一个没被划掉的数 7 (p=7)：

划掉 14、21、28（其中 14、21、28 已经被划掉了） 数列变成了：

最后保留下来的数：2357111317192329

2、对应的数学知识

2.1 为什么“划掉倍数”是正确的

如果一个数是某个整数  的倍数，说明它至少有两个因子：1、 和它本身以外的其他因子，所以它一定不是质数。

比如 12 是 2 的倍数，那么它至少有两个因子：1、2 和它本身以外的其他因子6，所以它一定不是质数。

2.2 为什么筛到  就可以停

如果  是合数，那么一定可以写成：

他们是成队出现的，我们对成队的因数进行按照大小进行分组分析：举例：一个数  的因数成对出现，例如：

• 100 的因数对是 (1, 100)、(2, 50)、(4, 25)、(5, 20)、(10, 10)

100的因数对中，小的因数分别是 1、2、4、5、10，而且100的因数对中的小因数肯定不会大于 。

★

因为，如果  是合数，如果他的因数对中小的因数大于 ，那么大的因数也大于 ，那两个数的乘积肯定大于 。比如100的因数对中不会存在(11,?),(12,?)这样的因数对，因为11和12都大于10了，那么他们的乘积肯定大于100了。

因此，如果  是合数，那么它的因数对中至少有一个小的因数不大于 。所以我们只需要检查 2 到  的整数即可判断  是否为质数。

2.3 为什么处理完一个数后，取下一个没有被划掉的数作为新的  继续划掉它的倍数？

因为这个数没有被划掉，说明他没有被小于他的数的倍数划掉过，所以小于他的数都不是他的因数，所以这个数一定是质数。

比如3没有被划掉，说明他没有被2的倍数划掉过，所以2不是3的因数，所以3一定是质数。

4被划掉了，说明他被2的倍数划掉过，所以2是4的因数，所以4不是质数。

3、数学建模

3.1 模型的输入和输出

1. 输入：一个正整数上限 n
2. 输出：2 到 n 之间全部质数

模型步骤

1. 输入并获取输入的n，确定处理范围
2. 初始化一个布尔列表 numList，长度为n+1,默认所有数都是质数（True），设置 numList[0] 和 numList[1] 为 False（因为 0 和 1 不是质数）
3. 从2开始，取没有被划掉的数 p（初始时 p=2），把它的倍数对应的 numList 元素设置为 False（划掉）
4. 重复步骤3，直到 p 的平方大于 n（即 p > sqrt(n)）为止
5. 最后，遍历 numList，把对应元素为 True 的索引收集起来，这些索引就是质数

4、Python 代码实现

import math# 1. 输入并获取输入的n，确定处理范围n = int(input("请输入数字n："))# 2. 初始化布尔列表，默认全部为True（代表是质数）numList = [True] * (n + 1)# 0和1不是质数，标记为FalsenumList[0] = FalsenumList[1] = False# 3、4：循环筛选，直到p平方大于n停止p = 2# p <= 根号n 时继续筛选while p <= math.sqrt(n):# 如果当前p是质数（没被划掉）if numList[p] == True:# 把p所有倍数标记为False（划掉合数）        multiple = p * 2while multiple <= n:            numList[multiple] = False            multiple = multiple + p# p自增，检查下一个数字    p = p + 1# 5. 收集所有值为True的下标，就是质数prime_list = []for index in range(n + 1):if numList[index] == True:        prime_list.append(index)# 输出结果print("2~n之间的质数：", prime_list)

5、示例输出

当输入 30 时，可能输出：

请输入数字n：302~n之间的质数： [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

6、复杂度与方法对比

• 逐个判断法（每个数都做质数判断）更直观，但重复计算多
• 埃氏筛更适合“求一段范围内的全部质数”

埃氏筛时间复杂度约为：

空间复杂度为：

当  较大时，筛法通常明显更快。