[笔记，科普，数学] 素数（9）：判定素数的埃拉托色尼筛 Sieve of Eratosthenes

埃拉托色尼筛： Sieve of Eratosthenes

埃拉托色尼： Eratosthenes of Cyrene, Eratosthenes, 大约公元前 276~194, 82

亚历山大，埃及： Alexandria, Egypt

素数定理： prime number theorem

素数间隙： prime gap

素数计数函数： prime counting function

   “埃拉托色尼筛 Sieve of Eratosthenes”是判定素数的一个简单的古老的方法。具体步骤如下：

   对于从 2 开始到指定范围 n 之间的正整数，

   （1）从 2 开始，划掉所有大于 2 且能被 2 整除的整数；

   （2）找到剩余整数中“最小的整数”，划掉所有大于该“最小的整数”且能被该“最小的整数”整除的整数；

   （3）循环“根号 n 向下取整”次。剩下的就是所有的素数。

   埃拉托色尼筛 Sieve of Eratosthenes，

   时间复杂性： O(nlglgn) ， 

   占用空间： n ， 

演示“埃拉托色尼筛 Sieve of Eratosthenes”的一个动图：

图1  Agb5mPVOVZ-sieve_of_eratosthenes_animation.gif

https://d18l82el6cdm1i.cloudfront.net/uploads/Agb5mPVOVZ-sieve_of_eratosthenes_animation.gif

参考资料：

[1] 科普中国，2021-12-31，埃拉托斯特尼筛法

https://www.kepuchina.cn/article/articleinfo?business_type=100&classify=0&ar_id=212409

   埃拉托斯特尼筛法

   文章中描述的“从2开始，每隔一个数删去一个数”等操作，实际上是在介绍一种古老的寻找素数的方法——埃拉托斯特尼筛法（Sieve of Eratosthenes）。该方法由古希腊学者埃拉托斯特尼发明，用于找出一定范围内的所有素数。其原理是从小到大依次标记每个素数的倍数，剩下的未被标记的数即为素数。这是一种高效且易于理解的算法，常用于教学和初级编程练习。

[2] 科普中国，2021-12-31，素数分布

https://www.kepuchina.cn/article/articleinfo?business_type=100&classify=0&ar_id=315801

   素数分布是数论中研究素数性质的重要课题。素数或称质数，是指一个大于1的整数，除1和它本身外，不能被其他的正整数所整除。研究各种各样的素数分布状况，一直是数论中最重要和最有吸引力的中心问题之一。关于素数分布性质，通过数值观察、计算和初步研究发现，素数分布是以黎曼公式为中心，高斯公式为上限的正态分布，这在现在来说是经验公式，待数学家给出严格证明之后才能成为数学定理。

   素数在自然数中占有极其重要的地位，但是它的变化非常不规则。人们至今没有找到，大概也不可能找到一个可以表示全体素数的有用公式。最初的研究方法，是通过观察素数表来发现素数分布的性质。

以前的《科学网》相关博文链接：

[1] 2026-03-12 22:07，[打听，科普，数学] 素数（8）：素数间隙 prime gap 与 Cramer's Conjecture  (Cramér's Conjecture)

https://blog.sciencenet.cn/blog-107667-1525561.html  

[2] 2026-03-11 23:01，[打听，科普，数学] 素数（7）：素数间隙 prime gap 之一

https://blog.sciencenet.cn/blog-107667-1525421.html

[3] 2026-03-10 20:54，[打听，科普，数学] 素数（6）：不用黎曼猜想的“素数计数函数”2个估计

https://blog.sciencenet.cn/blog-107667-1525254.html

[4] 2026-03-09 22:12，[笔记，科普，数学] 素数（5）：黎曼猜想 Riemann Hypothesis

https://blog.sciencenet.cn/blog-107667-1525092.html

[5] 2026-03-08 21:01，[笔记，科普，数学] 素数（4）：素数定理，黎曼两个估计的误差

https://blog.sciencenet.cn/blog-107667-1524948.html

[6] 2026-03-07 21:01，[笔记，科普，数学] 素数（3）：素数定理，高斯两个估计的误差

https://blog.sciencenet.cn/blog-107667-1524859.html

[7] 2026-03-05 21:30，[笔记，科普，数学] 素数（2）：素数定理 prime number theorem 之一

https://blog.sciencenet.cn/blog-107667-1524561.html

[8] 2026-03-04 15:36，[笔记，科普，数学] 素数（1）：算术基本定理 fundamental theorem of arithmetic

https://blog.sciencenet.cn/blog-107667-1524368.html

[9] 2024-11-17 22:51，[数学文化，客观派，讨论] 欧几里得对“素数有无穷多个”研究的有效性

https://blog.sciencenet.cn/blog-107667-1460458.html

[10] 2024-11-10 22:51，[数学文化，笔记] 素数有无穷多个之九类证明

https://blog.sciencenet.cn/blog-107667-1459433.html

[11] 2024-11-02 22:49，[笔记，科普，资料] 素数 prime number 入门

https://blog.sciencenet.cn/blog-107667-1458252.html

[12] 2013-07-23 11:51，孪生素数：相关介绍和链接

https://blog.sciencenet.cn/blog-107667-710546.html

[13] 2024-10-22 22:21，[打听，笔记] 推导符号公式的局限性：从数学、心理学到哲学

https://blog.sciencenet.cn/blog-107667-1456506.html

[14] 2024-05-19 22:49，[羡慕，讨论，物理] 仅推公式就能得到成果的人

https://blog.sciencenet.cn/blog-107667-1434748.html

[15] 2026-01-21 20:45，[往日（22）] 外国 Science 文献给出“人类最高成就”者的部分统计原因（相关性）：宽基础、重积累

https://blog.sciencenet.cn/blog-107667-1519414.html

[16] 2026-03-06 01:24，[资源，科普，数学] 素数表（质数表，小于 200000） list of primes, prime numbers

https://blog.sciencenet.cn/blog-107667-1524570.html

[17] 2024-06-25 22:49，[请教，讨论，笔记] 柯西：函数不一定要有解析表达式。（关联：分布参数系统 distributed parameter system）

https://blog.sciencenet.cn/blog-107667-1439715.html

感谢您的指教！

感谢您指正以上任何错误！

感谢您提供更多的相关资料！