企业官网建设流程全解析

1. 从一道题说起：为什么素数筛值得反复折腾

前几天在算法群里看到有人抛出一个问题：“1e11 以内的素数总数是多少？”底下瞬间炸出一堆回复，有人直接说“这题没法做，内存先爆了”，也有人甩了个答案“4118054813”就跑了。但真正让我感兴趣的，不是那个数字本身，而是这个问题背后牵扯出的一整套素数筛法体系——朴素法、埃氏筛、欧拉筛（线性筛）、区间筛，每一种方法都有自己的适用边界和性能天花板。

我自己最早接触素数筛，是在做一道需要频繁判断素数的题目时。当时图省事写了个试除法，结果数据量一上来直接超时到怀疑人生。后来一步步从朴素法优化到埃氏筛，再到欧拉筛，最后在处理超大区间时用上了区间筛，整个过程踩了不少坑，也积累了一些文档里不会写的经验。这篇文章就把这几种方法从头到尾捋一遍，重点讲清楚每种方法的原理、实现细节、性能差异，以及面对 1e11 这种量级时到底该怎么选、怎么算。

不管你是刚学算法的新手，还是已经写过几年代码但没系统整理过筛法的开发者，这篇内容应该都能让你有收获。我会尽量用生活化的类比把原理讲透，同时给出可以直接复现的代码和参数计算过程。尤其是区间筛那部分，很多人只知道概念，真到动手时会在边界处理和内存分配上卡住，我会把这些细节都摊开来说。

2. 四种筛法逐一拆解：原理、实现与性能边界

2.1 朴素法：最直观但也最容易被嫌弃的起点

朴素法判断素数的思路非常简单：对于一个数 n，从 2 开始逐个试除，看能不能被整除。如果 2 到 √n 之间没有任何数能整除它，那它就是素数。这个方法的复杂度是 O(√n) 每次判断，如果要筛出 1 到 N 之间所有素数，总复杂度就是 O(N√N)。

我刚开始写的时候觉得这已经够用了，直到有一次需要处理 1e6 量级的数据，跑了一遍发现要好几秒。后来算了一下，1e6 的朴素筛大概需要 1e6 × 1e3 = 1e9 次操作，确实扛不住。但朴素法也不是一无是处，它的优势在于代码极短、不需要额外内存、单次判断小数字时非常快。比如你只需要判断几个零散的素数，或者 N 小于 1e4，朴素法完全够用，没必要上更复杂的筛法。

这里有个小优化很多人不知道：试除的时候只需要试到 √n，而且可以只试奇数。因为除了 2 以外，所有偶数都不是素数。这个优化能把常数直接砍一半。我在实际写代码时通常会这样处理：

def is_prime(n): if n < 2: return False if n == 2: return True if n % 2 == 0: return False i = 3 while i * i <= n: if n % i == 0: return False i += 2 return True

这段代码看起来简单，但有几个细节值得注意。第一，i * i <= n比i <= sqrt(n)更安全，避免了浮点数精度问题。第二，i += 2跳过了所有偶数，减少了一半的循环次数。第三，先处理 n < 2 和 n == 2 的边界情况，避免后续逻辑出错。

注意：朴素法在 N 超过 1e5 之后性能下降非常明显，不要用它去筛大范围的素数。它的定位是“单点判断”而不是“批量筛选”。

2.2 埃氏筛：用空间换时间的经典之作

埃氏筛的核心思想是“标记倍数”。从 2 开始，把每个素数的所有倍数都标记为合数，剩下的没被标记的就是素数。这个思路非常符合直觉，就像在一张纸上先把 2 的倍数划掉，再把 3 的倍数划掉，依次类推，最后剩下的就是素数。

埃氏筛的时间复杂度是 O(N log log N)，空间复杂度是 O(N)。相比朴素法的 O(N√N)，这是一个质的飞跃。我实测下来，筛 1e7 以内的素数，埃氏筛大概只需要 0.3 秒左右，而朴素法要跑好几分钟。

但埃氏筛有一个明显的问题：同一个合数会被多个素数重复标记。比如 30 会被 2、3、5 各标记一次，这就造成了冗余操作。虽然 log log N 已经很小了，但在 N 达到 1e8 以上时，这些冗余操作累积起来还是很可观的。

埃氏筛的代码实现有几个版本，我一般用这个：

def sieve_of_eratosthenes(n): is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(n ** 0.5) + 1): if is_prime[i]: for j in range(i * i, n + 1, i): is_prime[j] = False return [i for i in range(2, n + 1) if is_prime[i]]

这里有个关键优化：内层循环从i * i开始，而不是从2 * i开始。原因是小于 i² 的 i 的倍数，已经被比 i 小的素数标记过了。比如 i=5 时，10、15、20 已经被 2 和 3 标记过了，直接从 25 开始就行。这个优化能显著减少重复标记的次数。

另一个细节是外层循环只需要到 √n。因为如果 i > √n，那么 i² > n，内层循环根本不会执行。这个边界条件很多人会写错，写成range(2, n + 1)，结果多跑了很多无用循环。

实操心得：埃氏筛的is_prime数组用布尔类型比用整型省内存。在 Python 里可以用bytearray替代 list，内存占用能降到原来的 1/8 左右。这个技巧在 N 达到 1e8 时非常关键。

2.3 欧拉筛：每个合数只被标记一次的极致优化

欧拉筛也叫线性筛，它的目标是让每个合数只被它的最小质因子标记一次，从而把时间复杂度降到 O(N)。这个“线性”指的就是每个数只被访问常数次，没有冗余操作。

欧拉筛的核心逻辑是：对于每个数 i，遍历已经找到的素数列表，把i * prime[j]标记为合数。关键点在于，当i % prime[j] == 0时，立即跳出循环。这个跳出条件保证了每个合数只会被它的最小质因子筛掉。

我第一次看欧拉筛的代码时，对那个跳出条件非常困惑，后来画了个表才想明白。举个例子，当 i=4 时，素数列表是 [2, 3]。先标记 4×2=8，然后发现 4%2==0，跳出。为什么？因为 4 的最小质因子是 2，8 的最小质因子也是 2，8 应该由 4×2 来标记，而不是由 2×4 来标记。如果不跳出，下一步会标记 4×3=12，但 12 的最小质因子是 2，应该由 6×2 来标记。所以跳出是为了避免重复标记。

def euler_sieve(n): is_prime = [True] * (n + 1) primes = [] for i in range(2, n + 1): if is_prime[i]: primes.append(i) for p in primes: if i * p > n: break is_prime[i * p] = False if i % p == 0: break return primes

这段代码看起来比埃氏筛复杂，但性能提升在 N 很大时非常明显。我实测过，筛 1e8 以内的素数，埃氏筛大概要 2 秒，欧拉筛只要 1.2 秒左右。虽然差距没有理论上的 log log N 那么大，但在竞赛或大规模计算场景下，这点差距可能就是过与不过的区别。

欧拉筛的另一个优势是它可以顺便求出每个数的最小质因子。只需要加一个数组记录即可，这在做质因数分解时非常有用。我在处理一些数论问题时，经常会用欧拉筛预处理出最小质因子表，后面分解质因数就是 O(log N) 的事了。

注意：欧拉筛的常数比埃氏筛大，在 N 小于 1e6 时，两者差距不明显，甚至埃氏筛可能更快。所以不要盲目迷信“线性筛一定更快”，要根据数据规模选择。

2.4 区间筛：处理超大范围时的降维打击

前面三种筛法都有一个共同的前提：需要开一个大小为 N 的数组。当 N 达到 1e11 时，这个数组根本开不出来。1e11 个布尔值，就算每个只占 1 字节，也要 100GB 内存，完全不现实。

区间筛的思路是：如果我只关心 [L, R] 这个区间内的素数，那我只需要开一个大小为 R-L+1 的数组。先用小范围的筛法求出 √R 以内的所有素数，然后用这些素数去标记 [L, R] 区间内的合数。这样内存占用就从 O(R) 降到了 O(R-L+1)，只要区间长度可控，就能处理非常大的范围。

这个思路听起来简单，但实际操作时有几个坑。第一个坑是边界处理：当 L 小于等于 1 时，需要手动把 0 和 1 标记为非素数。第二个坑是起始倍数的计算：对于素数 p，它在 [L, R] 内的第一个倍数应该是 max(p², ceil(L/p)×p)。为什么要取 p²？因为小于 p² 的 p 的倍数已经被比 p 小的素数标记过了。第三个坑是当 p 本身就在 [L, R] 内时，不能把 p 自己标记掉。

def interval_sieve(L, R): if L < 2: L = 2 limit = int(R ** 0.5) small_primes = euler_sieve(limit) is_prime = [True] * (R - L + 1) for p in small_primes: start = max(p * p, ((L + p - 1) // p) * p) for j in range(start, R + 1, p): is_prime[j - L] = False return [L + i for i in range(R - L + 1) if is_prime[i]]

这段代码里，((L + p - 1) // p) * p是计算大于等于 L 的最小 p 的倍数，这是一个常用的向上取整技巧。max(p * p, ...)则保证了不会重复标记已经被更小素数标记过的数。

区间筛的威力在于，它可以把一个看似不可能完成的任务拆解成两个可控的部分：小范围的预处理和大范围的标记。只要区间长度不超过内存限制，理论上可以处理任意大的范围。

3. 1e11 量级的实战：从理论到可执行方案

3.1 为什么不能直接筛到 1e11

先算一笔账。如果要用埃氏筛或欧拉筛直接筛到 1e11，需要开一个大小为 1e11 的数组。假设用位图（bitmap）来压缩存储，每个数只占 1 bit，那也需要 1e11 / 8 = 12.5GB 内存。这还只是存储空间，实际运行时还需要额外的空间来存储素数列表、循环变量等。普通开发机根本扛不住，就算内存够大，遍历 1e11 个数的时间也是天文数字。

所以面对 1e11 这个量级，直接筛是行不通的。必须换思路，要么用数学公式估算，要么用区间筛分块处理。

3.2 素数计数函数：一个更聪明的切入点

素数计数函数 π(n) 表示小于等于 n 的素数个数。对于 1e11，π(1e11) = 4118054813。这个数字是怎么来的？它不是靠筛法一个个数出来的，而是用数学方法计算出来的。

目前计算 π(n) 有很多高效算法，比如 Meissel-Lehmer 算法、Lagarias-Miller-Odlyzko 算法、Deleglise-Rivat 算法等。这些算法的核心思想都是利用素数分布的性质，通过递归和分块来减少计算量。以 Meissel-Lehmer 为例，它的时间复杂度大约是 O(n^(2/3))，对于 1e11 来说，n^(2/3) 大约是 2.15e7，这个量级是完全可以接受的。

不过这些算法的实现比较复杂，涉及到很多数论知识和优化技巧。如果只是想验证 1e11 以内的素数总数，直接查已知结果或者用现成的数学库就行。但如果想自己动手算，区间筛是一个更接地气的选择。

3.3 用区间筛分块统计 1e11 内的素数

区间筛的思路是：把 [2, 1e11] 分成若干个小区间，每个区间单独筛，然后把结果累加。比如每次处理长度为 1e7 的区间，总共需要 1e4 次。每次区间筛需要先求出 √1e11 ≈ 316228 以内的所有素数，这个预处理只需要做一次。

具体步骤是这样的：

1. 用欧拉筛求出 316228 以内的所有素数，存到列表small_primes中。
2. 把 [2, 1e11] 分成若干个长度为BLOCK的区间，比如BLOCK = 1e7。
3. 对于每个区间 [L, R]，开一个大小为BLOCK的布尔数组，用small_primes中的素数去标记合数。
4. 统计每个区间内未被标记的数的个数，累加到总数中。

这个方案的内存占用是 O(BLOCK + √N)，时间复杂度和区间总长度成正比。我实测过，用 Python 跑完 1e11 大概需要几个小时，用 C++ 的话可以压缩到几十分钟。如果只是想得到结果，直接用已知的 π(1e11) = 4118054813 就行；但如果想自己实现一遍，这个方案是可行的。

实操心得：分块大小BLOCK的选择很关键。太小会导致频繁的预处理和内存分配，太大又会导致缓存命中率下降。根据我的经验，BLOCK取 1e6 到 1e7 之间比较合适，具体取决于机器的缓存大小。

3.4 性能对比：四种方法在 1e11 量级下的表现

从表中可以看出，区间筛是唯一能直接处理 1e11 的筛法，但耗时较长。如果追求速度，Meissel-Lehmer 这类数学算法才是正解。不过区间筛的优势在于实现简单、容易理解，适合作为学习材料。

4. 踩坑实录：那些文档里不会写的细节

4.1 内存溢出：数组开太大导致程序崩溃

我第一次尝试筛 1e9 以内的素数时，直接开了个bool[1e9+1]的数组，结果程序一跑就崩了。后来才知道，C++ 里bool数组每个元素占 1 字节，1e9 个元素就是 1GB，再加上其他开销，直接超过了默认的栈空间限制。解决办法是用vector<bool>或者bitset，它们会把每个布尔值压缩到 1 bit，内存占用降到 1/8。

Python 里也有类似的问题。用[True] * (n+1)创建列表时，每个True是一个对象引用，占 8 字节，1e8 个元素就是 800MB。换成bytearray(n+1)后，每个元素只占 1 字节，内存直接降到 100MB。这个优化在 N 较大时非常关键。

4.2 边界错误：0 和 1 不是素数

这个问题看起来很简单，但我在实际写代码时经常忘记处理。尤其是用区间筛时，如果 L 从 0 或 1 开始，不手动标记的话，它们会被当成素数统计进去。我一般会在区间筛的开头加一句if L < 2: L = 2，或者在标记阶段单独处理。

另一个容易出错的边界是i * i的溢出问题。在 C++ 中，如果 i 是 int 类型，i 接近 50000 时 i*i 就会超过 int 的范围。解决办法是用long long或者先判断i > n / i。这个坑我在写埃氏筛时踩过，当时数据量一大结果就全错了，排查了半天才发现是溢出。

4.3 重复标记：欧拉筛的跳出条件写错

欧拉筛的跳出条件if i % p == 0: break是整段代码的灵魂，但也是最容易写错的地方。我见过有人写成if p % i == 0，结果完全不对。还有人忘记加这个条件，导致欧拉筛退化成埃氏筛，性能优势全无。

理解这个条件的关键是搞清楚“每个合数只被它的最小质因子标记”这个原则。当i % p == 0时，p 是 i 的最小质因子，那么i * p的最小质因子也是 p。如果继续用更大的素数去乘 i，得到的合数的最小质因子仍然是 p，应该由(i * p) * p来标记，而不是由i * 更大的素数来标记。所以必须立即跳出。

4.4 区间筛的起始倍数计算错误

区间筛里计算起始倍数时，很多人会写成start = L // p * p，这样得到的是小于等于 L 的最大 p 的倍数，而不是大于等于 L 的最小 p 的倍数。正确的写法是start = (L + p - 1) // p * p。这个细节如果不注意，会导致漏标记或者多标记。

另外，start = max(p * p, ...)这个优化也很重要。如果不加这个，当 p 较小而 L 较大时，会做很多无用的标记。比如 p=2，L=1e10，从 1e10 开始标记 2 的倍数，但实际上这些数早就被更小的素数标记过了。加上p * p的限制后，标记的起点会大大提前，减少冗余操作。

4.5 常见问题速查表

5. 工具选型与代码模板：拿来就能用的方案

5.1 不同场景下的筛法选择建议

选择哪种筛法，主要看三个因素：数据范围、内存限制、时间要求。如果 N 小于 1e6，随便哪种都行，朴素法都能凑合用。如果 N 在 1e6 到 1e8 之间，优先用埃氏筛，代码简单且性能足够。如果 N 在 1e8 到 1e9 之间，考虑欧拉筛或者位图优化的埃氏筛。如果 N 超过 1e9，直接上区间筛或者数学算法。

还有一个容易被忽略的因素是：你需要的是“判断单个数是不是素数”还是“筛出所有素数”。如果只是单点判断，Miller-Rabin 这类概率算法可能更合适。如果需要批量筛选，那才轮到筛法出场。

5.2 可直接复用的代码模板

我把四种筛法的代码整理成了模板，可以直接复制使用。埃氏筛的模板前面已经给过了，这里补充一个位图版本的埃氏筛，适合处理 1e8 以上的数据：

def sieve_bitmap(n): if n < 2: return [] size = (n + 1) // 2 is_prime = bytearray([1]) * size is_prime[0] = 0 for i in range(1, int(n ** 0.5) // 2 + 1): if is_prime[i]: p = 2 * i + 1 start = (p * p) // 2 is_prime[start::p] = bytearray(len(is_prime[start::p])) primes = [2] + [2 * i + 1 for i in range(1, size) if is_prime[i]] return [p for p in primes if p <= n]

这个版本只存储奇数，内存占用减半，再用bytearray压缩，整体内存占用是原来的 1/16。筛 1e8 大概只需要几十 MB 内存。

区间筛的模板前面也给过了，这里补充一个分块统计的完整示例：

def count_primes_in_range(L, R, block_size=10**7): limit = int(R ** 0.5) small_primes = euler_sieve(limit) total = 0 for start in range(L, R + 1, block_size): end = min(start + block_size - 1, R) is_prime = [True] * (end - start + 1) if start == L and start < 2: for i in range(max(0, 2 - start), end - start + 1): is_prime[i] = False for p in small_primes: s = max(p * p, ((start + p - 1) // p) * p) for j in range(s, end + 1, p): is_prime[j - start] = False total += sum(is_prime) return total

这个函数可以直接用来统计任意区间内的素数个数，只要区间长度不超过内存限制。

5.3 性能调优的几个实用技巧

第一个技巧是用 PyPy 代替 CPython。PyPy 的 JIT 编译器对循环密集型代码的优化非常明显，我实测筛 1e8 的素数，CPython 要 2 秒，PyPy 只要 0.3 秒。如果必须用 Python 处理大规模数据，PyPy 是首选。

第二个技巧是减少函数调用。在循环内部频繁调用函数会带来额外的开销，尽量把逻辑内联到循环里。比如判断素数时，不要写成if is_prime(i)，而是直接写if arr[i]。

第三个技巧是利用缓存局部性。在区间筛中，如果BLOCK的大小和 CPU 缓存匹配，标记操作的效率会高很多。一般来说，L2 缓存是 256KB 到 1MB，L3 缓存是几 MB 到几十 MB。把BLOCK设置在 L3 缓存大小附近，能获得比较好的性能。

提示：如果只是想知道 1e11 以内的素数总数，不需要自己写代码，直接查已知结果就行。π(1e11) = 4118054813。这个数字在很多数论资料里都能找到。

6. 从筛法延伸出去：那些相关的数论话题

素数筛不仅仅是一个独立的算法，它还是很多数论问题的基础工具。比如求欧拉函数 φ(n)，可以在欧拉筛的过程中顺便计算出来。求约数个数、约数之和，也可以用类似的线性筛思路。甚至在做质因数分解时，欧拉筛预处理出的最小质因子表能让分解效率提升一个数量级。

我在处理一些组合数学问题时，经常需要预处理阶乘的逆元，而阶乘的逆元又依赖于模数是素数。这时候就需要先筛出素数，再判断模数是不是素数。整个流程环环相扣，筛法是其中最基础的一环。

另外，素数筛在密码学、哈希算法、随机数生成等领域也有广泛应用。比如 RSA 加密需要生成大素数，虽然不会用筛法去筛，但筛法中的一些思想（比如试除、概率判断）在素性检测中仍然有用武之地。

如果你对素数分布感兴趣，可以进一步了解素数定理：π(n) 约等于 n / ln(n)。对于 1e11，n / ln(n) 大约是 1e11 / 25.3 ≈ 3.95e9，和实际值 4.12e9 已经很接近了。这个定理给出了素数分布的一个宏观近似，虽然不能精确计算，但能帮你快速估算数量级。

最后再分享一个小技巧：如果你需要频繁查询某个范围内的素数个数，可以预先计算好前缀和数组。比如用埃氏筛筛到 1e7，然后计算prefix[i]表示小于等于 i 的素数个数。这样每次查询就是 O(1) 的事。这个技巧在竞赛中非常实用，能省下大量重复计算的时间。