[笔记，科普，数学] 素数（10）：判定素数的欧拉筛 sieve of Euler

欧拉筛： sieve of Euler

埃拉托色尼筛： Sieve of Eratosthenes

素数定理： prime number theorem

素数间隙： prime gap

素数计数函数： prime counting function

一、欧拉筛法步骤

https://www.cnblogs.com/kentle/p/14205126.html

   （1）读取输入的数 n，将 2 至 n 所有整数记录在表中

   （2）从 i=2 开始，如果 i 在表中，则将 i 加入至素数列表中

   （3）遍历当前素数列表，筛去 i 素数倍的数

   （4）当遍历到能整除 i 的素数 p 时，筛去 i·p，停止对素数列表的遍历

   （5）重复 2, 3, 4，直到所有不超过 n 的整数都被遍历过

   （6）素数列表中的元素即为所求的不超过 n 的所有素数

   (1) First, make a list of numbers from 2, as large as you wish; call the maximum number n.

   (2) Second, extract the first number from the list, make a new list in which each element of the original list, including the first, is multiplied by the extracted first number.

   (3)Third, “subtract” the new list from the original, keeping in an output list only those numbers in the original list that do not appear in the new list.

   (4) Fourth, output the first number from the list, which is prime, and repeat the second, third and fourth steps on the reduced list excluding its first element, continuing until the input list is exhausted.

   时间复杂性：O(n) , 。

   空间复杂性：O(n) , 。

二、欧拉筛法过程举例

图1  修改自：欧拉筛 11 8b80a01d8061118223f171d4b13495e3.png

https://i-blog.csdnimg.cn/blog_migrate/8b80a01d8061118223f171d4b13495e3.png

图2  修改自：欧拉筛 22 343ae02cce3dfe0a16180df21837b94b.png

https://i-blog.csdnimg.cn/blog_migrate/343ae02cce3dfe0a16180df21837b94b.png

图3  修改自：欧拉筛 33 8125876d4fbc11c31717a1941046021d.png

https://i-blog.csdnimg.cn/blog_migrate/8125876d4fbc11c31717a1941046021d.png

图4  欧拉筛（线性筛）过程

修改自：aishisai.png

https://www.mustenaka.cn/wp-content/uploads/2020/04/aishisai.png

参考资料：

[1] 博客园，2021-03-27 19:16，素数筛法算法及其原理

https://www.cnblogs.com/kentle/p/14205126.html

[2] CSDN，2021-08-27 19:39:37，素数筛 欧拉函数

https://blog.csdn.net/qq_54886579/article/details/119958593

[3] 木十的博客，2020-04-23，求解素数的三种方法

https://www.mustenaka.cn/index.php/2020/04/23/primenumbersinpython/

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

[1] 2026-3-13 22:49，[笔记，科普，数学] 素数（9）：判定素数的埃拉托色尼筛 Sieve of Eratosthenes

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

感谢您的指教！

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

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