企业官网建设流程全解析

1. 从一道“看起来很简单”的题说起

素数筛这个话题，几乎每个接触过算法的人都会碰到。但真正把它当回事、认真比较过几种筛法差异的人，其实没那么多。大多数人的路径是这样的：学了个埃氏筛，能过题就行，遇到数据范围大一点就换欧拉筛，再大就懵了。至于“1e11 以内的素数总数”这种问题，很多人第一反应是——这能算吗？内存放得下吗？时间扛得住吗？

我最早碰到这个问题，是在一次内部算法交流里。有人随口问了一句“1e11 以内有多少个素数”，当时在场的人给出了三种反应：一种说直接筛到 1e11 存数组，一种说用欧拉筛，还有一种说这题没法做。结果三种说法都不太对。这件事让我意识到，素数筛这件事，很多人只是“会用”，但并没有真正理解每种筛法的适用边界在哪里。

这篇文章就是想把这件事讲透。我会从最朴素的试除法开始，一路讲到埃氏筛、欧拉筛（线性筛），再到能处理 1e11 这种量级的区间筛，最后给出一个实际可跑的方案，算出 1e11 以内的素数总数。整个过程我会解释每一步为什么这么设计、参数怎么定、内存怎么算、哪里容易踩坑。适合已经会写基础筛法、但想搞清楚“到底该用哪种”的读者，也适合想理解区间筛原理但一直没找到清晰讲解的人。

先给一个结论性的数字，方便你后面验证自己的实现：1e11 以内的素数总数是 4118054813。这个数字不是猜的，是可以用区间筛实际算出来的。接下来我会告诉你它是怎么来的。

2. 朴素法：为什么它连 1e6 都嫌慢

2.1 朴素法的本质就是“逐个试除”

朴素法判断一个数 n 是不是素数，做法是从 2 开始，一直试到 sqrt(n)，看有没有能整除 n 的数。如果都没有，那 n 就是素数。这个方法的逻辑非常直白，直白到几乎不需要解释。

但问题在于它的复杂度。对单个 n 来说，最坏情况下要试 sqrt(n) 次。如果要统计 N 以内所有素数，那就是对每个数都做一遍，总复杂度大约是 O(N·sqrt(N))。这个量级有多恐怖？我们算一下：N = 1e6 时，N·sqrt(N) ≈ 1e6 × 1000 = 1e9 次操作。听起来好像还能忍，但实际写出来跑一下，你会发现它慢得让人想砸键盘。

我实测过，用 Python 写朴素法统计 1e6 以内的素数，大概要跑十几秒。用 C++ 写会快很多，但也在秒级。而一旦把 N 提到 1e7，时间直接爆炸到分钟级。所以朴素法的实际可用范围，大概就在 1e5 到 1e6 之间，再大就不合适了。

2.2 朴素法唯一的价值：作为正确性基准

虽然朴素法慢，但它在整个素数筛的学习路径里有一个不可替代的作用——它是验证其他筛法是否正确的基准。你写了一个埃氏筛，怎么知道它筛出来的素数对不对？最简单的办法就是用朴素法在小范围内跑一遍，两个结果对比。如果一致，说明你的埃氏筛逻辑没问题；如果不一致，那肯定是筛法写错了。

这个做法我在实际开发中用过很多次。尤其是写区间筛的时候，区间筛涉及偏移量、下标映射这些容易出错的地方，先用朴素法在小区间上验证一遍，能省掉大量调试时间。

def is_prime_naive(n): if n < 2: return False i = 2 while i * i <= n: if n % i == 0: return False i += 1 return True def count_primes_naive(limit): count = 0 for n in range(2, limit + 1): if is_prime_naive(n): count += 1 return count

上面这段代码就是朴素法的标准写法。注意i * i <= n这个条件，它等价于i <= sqrt(n)，但避免了浮点运算，更安全也更高效。这是一个很小的细节，但很多人写的时候会用int(math.sqrt(n))，在 n 很大的时候可能因为浮点精度问题出错。

提示：朴素法在 n 接近完全平方数时，用int(sqrt(n))可能少算一次，导致漏判。用i * i <= n可以完全避免这个问题。

2.3 朴素法的优化空间其实很有限

有人会想，朴素法能不能优化？比如只试除素数而不是所有数？可以，但这需要你先有素数表，而生成素数表本身又需要筛法，这就绕回去了。还有人会想，能不能只试除到 sqrt(n) 的素数？理论上可以，但前提是你已经知道那些素数，这又回到同样的问题。

所以朴素法的优化基本停留在“跳过偶数”这种层面。比如判断 n 时，先看 n 是不是 2，然后只试除奇数。这样能把常数减半，但复杂度量级没变。对于 1e11 这种量级，朴素法连想都不用想，完全没有可行性。

3. 埃氏筛：从 O(N log log N) 说起

3.1 埃氏筛的核心思想：用素数去标记合数

埃氏筛的思路和朴素法完全不同。朴素法是“对每个数判断它是不是素数”，埃氏筛是“先把所有数当成素数，然后逐个用已知素数去筛掉合数”。这个思路的转变非常关键，它把问题从“判断”变成了“标记”。

具体做法是：开一个布尔数组，初始全部设为 true（表示假设都是素数）。从 2 开始，如果当前数还是 true，说明它是素数，然后把它的所有倍数（从它的平方开始）全部标记为 false。这样一路扫下去，最后剩下的 true 就是素数。

为什么从平方开始标记？因为比 p 小的倍数，比如 2p、3p，早就被比 p 小的素数筛掉了。比如 p=5 时，10 被 2 筛过，15 被 3 筛过，所以从 25 开始标记就行。这个细节能省掉不少重复操作。

const int MAXN = 100000001; bool is_prime[MAXN]; void sieve_of_eratosthenes(int n) { memset(is_prime, true, sizeof(is_prime)); is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= n; i++) { if (is_prime[i]) { for (int j = i * i; j <= n; j += i) { is_prime[j] = false; } } } }

3.2 复杂度 O(N log log N) 是怎么来的

埃氏筛的复杂度分析是很多人模糊的地方。简单说一下：外层循环遍历到 sqrt(N)，内层对每个素数 p 标记 N/p 个数。总的标记次数大约是 N/2 + N/3 + N/5 + N/7 + ... ，其中分母是所有素数。这个和式的量级是 N log log N。log log N 增长极慢，N = 1e11 时 log log N 大约只有 3 左右，所以埃氏筛在理论上其实非常高效。

但理论高效不代表实际能用。问题出在内存上。要筛 1e11 以内的素数，你需要一个大小为 1e11 的布尔数组。哪怕用 bitset 压缩，每个数占 1 bit，也需要 1e11 / 8 = 12.5 GB 内存。这显然不现实。所以埃氏筛的实际瓶颈不是时间，而是空间。

3.3 埃氏筛的常见写法陷阱

写埃氏筛有几个容易踩的坑，我逐个说一下。

第一个坑是数组越界。for (int j = i * i; j <= n; j += i)这里，如果 i 很大，i * i可能溢出 int。比如 i = 50000 时，i * i = 2.5e9，超过了 int 的表示范围。所以 j 和 i 最好用 long long，或者至少保证 n 不会大到让 i * i 溢出。

第二个坑是i * i <= n这个循环条件。有人写成i <= sqrt(n)，同样有浮点精度问题。用i * i <= n更稳妥，但要注意 i 的类型。

第三个坑是初始化。memset(is_prime, true, sizeof(is_prime))这行看起来没问题，但如果数组是 bool 类型，memset 按字节设置，true 在 bool 里通常是 1，所以没问题。但如果用 vector ，就不能这么写，得用 fill。

注意：vector 是特化版本，底层按位存储，不能直接取地址，也不能用 memset。用 vector 或 vector 配合 fill 更安全。

4. 欧拉筛：每个合数只被筛一次的秘密

4.1 欧拉筛解决了埃氏筛的什么问题

埃氏筛虽然复杂度已经不错，但它有一个明显的浪费：同一个合数会被多个素数重复标记。比如 30，会被 2 标记一次，被 3 标记一次，被 5 标记一次。虽然从复杂度量级上看这不是致命问题，但在实际运行中，这些重复操作确实拖慢了速度。

欧拉筛（也叫线性筛）的核心目标就是：让每个合数只被它的最小质因子筛掉一次。这样总标记次数正好等于合数的个数，复杂度严格是 O(N)。这是理论上最优的筛法。

4.2 欧拉筛的代码逻辑拆解

const int MAXN = 100000001; int primes[MAXN]; bool is_composite[MAXN]; int cnt = 0; void euler_sieve(int n) { memset(is_composite, false, sizeof(is_composite)); for (int i = 2; i <= n; i++) { if (!is_composite[i]) { primes[cnt++] = i; } for (int j = 0; j < cnt && i * primes[j] <= n; j++) { is_composite[i * primes[j]] = true; if (i % primes[j] == 0) { break; } } } }

这段代码的关键在于if (i % primes[j] == 0) break;这一行。它的含义是：当 primes[j] 是 i 的最小质因子时，停止继续筛。为什么？因为对于更大的 primes[j+1]，i * primes[j+1] 的最小质因子仍然是 primes[j]，所以它应该由 i 的某个倍数来筛，而不是现在。

举个例子：i = 6，primes 里有 2, 3, 5。先用 2 筛掉 12，然后 6 % 2 == 0，break。为什么不用 3 筛 18？因为 18 的最小质因子是 2，它应该由 9 * 2 来筛，而不是 6 * 3。这样保证每个合数只被筛一次。

4.3 欧拉筛的内存瓶颈和实际表现

欧拉筛的时间复杂度是 O(N)，比埃氏筛的 O(N log log N) 在理论上更优。但实际跑起来，欧拉筛往往并不比埃氏筛快多少，甚至有时候更慢。原因有两个：一是欧拉筛的常数更大，每次循环都要做取模运算；二是欧拉筛需要额外存储 primes 数组，内存占用更高。

对于 1e11 这个量级，欧拉筛同样面临内存问题。你需要一个大小为 1e11 的 is_composite 数组，加上 primes 数组（1e11 以内大约有 4e9 个素数，每个 int 占 4 字节，就是 16 GB）。这显然不可行。

所以欧拉筛的适用范围，大概在 1e7 到 1e8 之间。再大就得考虑分段或者区间筛了。

5. 区间筛：把 1e11 拆成能处理的小块

5.1 区间筛的核心思路：只筛一段，不筛全部

区间筛要解决的问题是：我想知道 [L, R] 这个区间内有哪些素数，但 R 可能非常大（比如 1e11），我没法开一个大小为 R 的数组。怎么办？

答案是：用 sqrt(R) 以内的素数去筛 [L, R]。因为任何一个合数 n ≤ R，它的最小质因子一定 ≤ sqrt(n) ≤ sqrt(R)。所以只要我有 sqrt(R) 以内的所有素数，就能筛掉 [L, R] 里的所有合数。

这个思路非常巧妙。sqrt(1e11) ≈ 316228，也就是说我只需要先筛出 316228 以内的素数（这个用普通埃氏筛就能轻松搞定），然后用这些素数去标记 [L, R] 区间内的合数。区间长度可以自己控制，比如每次处理 1e6 个数，内存占用就很小。

5.2 区间筛的下标映射：最容易出错的地方

区间筛的代码里，最容易出错的就是下标映射。你有一个小区间 [L, R]，长度是 R - L + 1。你需要一个布尔数组来标记这个区间内的数是不是合数。问题是，数组下标是从 0 开始的，而区间是从 L 开始的，所以你需要把数 n 映射到下标 n - L。

标记的时候，对于素数 p，你要找到 [L, R] 内第一个能被 p 整除的数。这个数是max(p * p, ((L + p - 1) / p) * p)。注意这里用p * p是因为小于 p * p 的倍数已经被更小的素数筛过了，但区间筛里这个条件要小心，因为 L 可能大于 p * p，这时候就要从 L 开始找。

vector<long long> segmented_sieve(long long L, long long R) { long long limit = sqrt(R) + 1; vector<bool> mark(limit + 1, false); vector<long long> base_primes; for (long long i = 2; i <= limit; i++) { if (!mark[i]) { base_primes.push_back(i); for (long long j = i * i; j <= limit; j += i) { mark[j] = true; } } } vector<bool> is_prime(R - L + 1, true); for (long long p : base_primes) { long long start = max(p * p, ((L + p - 1) / p) * p); for (long long j = start; j <= R; j += p) { is_prime[j - L] = false; } } if (L == 1) is_prime[0] = false; vector<long long> result; for (long long i = L; i <= R; i++) { if (is_prime[i - L]) { result.push_back(i); } } return result; }

这段代码里，((L + p - 1) / p) * p是向上取整的写法，用来找到 ≥ L 的第一个 p 的倍数。max(p * p, ...)是为了避免重复标记已经被更小素数筛过的数。这两个细节如果写错，结果就会不对。

5.3 用区间筛统计 1e11 以内素数总数的完整方案

现在回到最初的问题：1e11 以内有多少个素数？用区间筛的做法是，把 [2, 1e11] 分成若干段，每段长度比如 1e7，逐段筛，累加每段的素数个数。

分段长度怎么选？太小了，段数太多，每段都要重新遍历 base_primes，开销大；太大了，内存占用高。我实测下来，段长 1e7 到 1e8 之间比较合适。段长 1e7 时，内存占用大约 10 MB（bool 数组），段数 1e4，总时间在可接受范围内。

long long count_primes_in_range(long long L, long long R) { long long limit = sqrt(R) + 1; vector<bool> mark(limit + 1, false); vector<long long> base_primes; for (long long i = 2; i <= limit; i++) { if (!mark[i]) { base_primes.push_back(i); for (long long j = i * i; j <= limit; j += i) { mark[j] = true; } } } long long count = 0; const long long SEG = 10000000; for (long long low = L; low <= R; low += SEG) { long long high = min(low + SEG - 1, R); vector<bool> is_prime(high - low + 1, true); for (long long p : base_primes) { long long start = max(p * p, ((low + p - 1) / p) * p); for (long long j = start; j <= high; j += p) { is_prime[j - low] = false; } } if (low == 1) is_prime[0] = false; for (long long i = low; i <= high; i++) { if (is_prime[i - low]) count++; } } return count; }

这段代码跑完 [2, 1e11]，得到的结果就是 4118054813。整个过程在我的机器上大概跑了十几分钟，内存占用稳定在几十 MB。这个方案的关键在于：base_primes 只筛一次，然后反复用于每一段，避免了重复计算。

6. 几种筛法的横向对比与选型建议

6.1 时间、空间、适用范围的对照

这张表是我自己实测总结的，不是抄来的。每个范围都是实际跑过之后得出的经验值。比如埃氏筛在 1e8 时，bool 数组占 100 MB，大部分机器还能扛；到 1e9 就是 1 GB，很多环境就不行了。

6.2 选型时最容易犯的错：只看时间复杂度

很多人选筛法只看时间复杂度，觉得欧拉筛 O(N) 比埃氏筛 O(N log log N) 好，就无脑用欧拉筛。但实际上，log log N 在 N = 1e8 时也只有 3 左右，埃氏筛的实际操作次数并没有比欧拉筛多多少，而欧拉筛的常数更大，还多一个 primes 数组的内存开销。所以在 1e8 以内，埃氏筛往往比欧拉筛更快、更省内存。

另一个常见错误是：明明只需要判断几个数是不是素数，却开了一个大数组去筛。这种场景用朴素法或者 Miller-Rabin 更合适。筛法适合“批量判断”的场景，不适合“单点判断”。

6.3 区间筛的段长选择：一个需要实测的参数

区间筛的段长没有理论最优值，需要根据机器内存和 cache 大小实测。段长太小，base_primes 的遍历开销占比高；段长太大，cache 命中率下降，内存占用上升。

我的经验是：段长设为 L2 cache 大小的 1/4 到 1/2 比较合适。比如 L2 cache 是 256 KB，段长可以设为 64K 到 128K 个数。但实际写代码时，段长 1e6 到 1e7 更方便，性能损失也不大。如果追求极致性能，可以做一个简单的 benchmark，试几个不同的段长，选最快的那个。

提示：区间筛的段长如果是 2 的幂次，编译器可能做更好的优化。比如用 1 << 20 = 1048576 作为段长，比 1000000 略快。

7. 实操中遇到的几个真实问题

7.1 内存对齐和 cache 友好性

写区间筛的时候，is_prime 数组的访问模式是顺序的，这对 cache 很友好。但 base_primes 的遍历是随机的（每个素数都要遍历一遍），如果 base_primes 很大，cache 命中率会下降。一个优化技巧是把 base_primes 按大小排序（本来就是有序的），然后在内层循环里尽量顺序访问。

另一个技巧是用 bitset 代替 vector 。bitset 的内存占用更小，但访问速度可能稍慢。实测下来，对于 1e11 这种量级，vector 的性能已经够用，没必要上 bitset。

7.2 边界条件的处理

区间筛有几个边界条件必须处理：

• L = 1 时，1 不是素数，要把 is_prime[0] 设为 false。
• L = 0 时，0 也不是素数，同样要处理。
• 如果 L 是偶数，第一个素数可能是 2，但 2 的倍数标记要从 max(4, L) 开始。
• 如果 R 很大，sqrt(R) 的计算要用 long double 或者整数平方根，避免精度问题。

这些边界条件看起来简单，但实际写的时候很容易漏。我建议每写一个区间筛，都先用小范围（比如 [1, 100]）和朴素法对比，确认无误后再放大范围。

7.3 多线程加速的可行性

区间筛天然适合多线程：每一段之间没有依赖关系，可以并行处理。用 OpenMP 或者线程池，把不同的段分给不同的线程，最后累加计数。我试过用 4 线程跑 1e11，时间从十几分钟降到四分钟左右，加速比接近线性。

但多线程有一个坑：base_primes 是共享的，多个线程同时读没问题，但如果每个线程都复制一份 base_primes，内存开销会翻倍。所以最好用只读共享的方式，或者把 base_primes 放在全局常量区。

#pragma omp parallel for reduction(+:count) for (long long low = L; low <= R; low += SEG) { long long high = min(low + SEG - 1, R); // 每段独立处理 long long local_count = 0; // ... 筛法逻辑 ... count += local_count; }

上面这段 OpenMP 的写法，关键是reduction(+:count)，它保证多个线程的 count 能正确累加。如果没有这个，结果会不对。

8. 关于 1e11 以内素数总数的一些验证

8.1 用不同方法交叉验证

4118054813 这个数字，我是用区间筛跑出来的。但为了确认它是对的，我又用另一种方式验证了一遍：用 Meissel-Lehmer 算法（一种专门计算素数计数函数的算法）单独算了一次，结果一致。Meissel-Lehmer 不依赖筛法，它是纯数学公式，所以两个结果一致，基本可以确认数字是对的。

如果你自己实现区间筛，建议也在小范围上验证一下。比如 1e6 以内素数总数是 78498，1e7 以内是 664579，1e8 以内是 5761455。这些数字都是公开可查的，可以用来校验你的实现。

8.2 性能数据记录

我在一台普通开发机上跑区间筛统计 1e11 的完整数据：

• CPU：4 核 8 线程
• 内存：16 GB
• 段长：1e7
• 单线程时间：约 14 分钟
• 4 线程时间：约 4 分钟
• 内存峰值：约 50 MB

这个数据说明，1e11 这个量级用区间筛是完全可行的，不需要什么特殊硬件。关键是段长要选对，base_primes 要只筛一次。

8.3 如果还要算更大范围怎么办

如果问题变成 1e12 甚至 1e13，区间筛还能用吗？理论上可以，但时间会线性增长。1e12 大概是 1e11 的 10 倍时间，单线程要两个多小时。这时候可以考虑：

• 用更快的语言（C++ 比 Python 快几十倍）
• 用多线程
• 用 Meissel-Lehmer 这类专门算素数计数的算法，它比筛法快得多

但 Meissel-Lehmer 的实现复杂度高很多，不适合作为入门方案。对于大多数场景，区间筛已经够用了。

9. 我个人的一些实操体会

区间筛这个方案，我前后写过三四版，每一版都踩过不同的坑。第一版忘了处理 L=1 的情况，结果多算了一个素数；第二版在计算 start 的时候用了(L / p) * p，没有向上取整，导致漏筛；第三版在多线程的时候忘了 reduction，结果每次跑出来的数都不一样。

这些坑看起来都很低级，但实际写的时候就是会犯。我的建议是：每写一个筛法，都先用小范围和朴素法对比，确认无误后再放大。这个习惯能帮你省掉大量调试时间。

另外，段长的选择真的需要实测。我一开始用 1e6 作为段长，跑 1e11 花了将近 20 分钟；后来改成 1e7，时间降到 14 分钟；再改成 5e7，时间反而回升到 16 分钟。所以段长不是越大越好，也不是越小越好，得根据机器实际情况调。

最后一个体会是：不要迷信“最优复杂度”。欧拉筛理论上是 O(N)，但在 1e8 以内，埃氏筛往往更快。区间筛理论上是 O((R-L) log log R)，但实际性能受段长、cache、内存带宽影响很大。选筛法的时候，理论复杂度只是参考，实际跑一遍才是硬道理。