企业官网建设流程全解析

很多刚开始学编程的人，动手写的第一个算法往往是“求素数”。这个题目看起来特别简单：输入一个数，判断它是不是素数；或者干脆把某个范围内的素数全部打印出来。但真正动手写的时候才发现，水比想象中深得多——边界情况、性能瓶颈、算法选型，每一个点都能展开聊半天。我见过不少人用最暴力的方式写完就没再管了，结果后面做加密算法、做数据筛选时又回头来补课。这篇把求素数这件事从头到尾掰开揉碎，从最基础的试除法讲到线性筛，再延伸到工程实践中真正用得上的优化思路，希望看完之后，不管是刚入学的新手还是写了几年业务代码的开发者，都能有所收获。

1. 关于素数，先把定义和边界问题聊透

1.1 素数的定义，以及总被人忽略的两个边界

数学课本上对素数的定义是：大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。注意，这里用了两个限定：大于 1，且只能被 1 和自身整除。那就存在两个经常被拿来出题的边界：1 不是素数也不是合数，2 是最小的素数，也是唯一的偶素数。

1 这个数字的特殊性其实很容易理解——如果 1 也算素数，那么“质因数分解唯一”这条基本定理就崩了，因为任何数字都能乘无数个 1。2 作为唯一的偶素数也很微妙，它是整个素数体系里唯一“破例”的偶数，这直接导致在写算法时可以做很多优化，比如判断完 2 之后，所有偶数直接就排除了。

1.2 “判断一个数是不是素数”和“找出一个范围内的所有素数”

在动手写代码之前，先要区分清楚需求到底属于哪一类。前者叫做素性检测，输入是一个数，输出是布尔值，这类场景在算法竞赛题和密码学里面很常见；后者叫做素数筛，输入是一个上限 N，输出是 [2, N] 之间的所有素数，这类场景在做数据预处理、统计区间分布时经常用到。

这两种需求对应完全不同的算法思路。判断单个数，试除法绰绰有余；但如果让你求 100 万以内所有素数，你再用单个数判断跑 100 万次，时间就完全扛不住了。所以很多初学者的第一步不是学算法，而是学会先搞清楚“我到底要解决哪个问题”，这一步想清楚了，选型才不会走弯路。

我在面试里问过不少候选人“求 100 以内素数”，有相当一部分人直接双层循环逐个判断，写完之后自己还觉得挺满意。其实只要稍微提示一句“这个范围很大，能不能一次筛一片”，思路立刻就不一样了。

2. 试除法：从最直觉的写法到性能翻倍

2.1 最朴素的写法与时间复杂度

判断 n 是不是素数，最直接的想法就是看 2 到 n-1 之间有没有能整除 n 的数，如果有，就是合数，反之就是素数。这个逻辑一个字都不用改，直接翻译成代码就行：

def is_prime_basic(n: int) -> bool: if n < 2: return False for i in range(2, n): if n % i == 0: return False return True

这段代码时间复杂度是 O(n)，如果对每个数都这样做，100 万以内的素数加起来就是 O(n²)，基本不可用。但作为理解算术定义的最直白表达，它对理解问题本身是很有帮助的。

可以先跑一下，比如判断 97 是不是素数，它真的会把 2 到 96 走一遍。哪怕是 97 这种明显感觉是素数的数，代码也老老实实从头试到尾，没有任何投机取巧，这就是暴力法的本质：用算力换思维，不行就是不行。

2.2 关键优化：只需要试到根号 n

这里有个数学定理经常被人遗忘：如果 n 是合数，那么它一定有一个不大于 sqrt(n) 的因数。证明也很简单，设 n = a × b，假设 a 和 b 都大于 sqrt(n)，那 a × b 肯定大于 n，矛盾。所以只要在 2 到 sqrt(n) 之间没有因数，那么 n 一定是素数。

这个改进瞬间把复杂度从 O(n) 降到 O(sqrt(n))：

import math def is_prime_sqrt(n: int) -> bool: if n < 2: return False if n == 2: return True if n % 2 == 0: return False limit = int(math.isqrt(n)) for i in range(3, limit + 1, 2): if n % i == 0: return False return True

这里还顺手做了一个小优化：先把 2 的情况单独处理，然后从 3 开始只检查奇数。原因很简单，偶数除了 2 之外全是合数，根本不需要判断。有人可能会纠结 math.isqrt 和 int(math.sqrt(n)) 的区别，isqrt 是整数开方，避免了浮点数误差问题，这种细节在 n 特别大时尤其值得注意。

2.3 更进一步：6k±1 形式优化

还有一个很经典的观察：除了 2 和 3 以外，所有素数都分布 6 的倍数附近，也就是说，形式要么是 6k-1，要么是 6k+1。你可以试着写下 5、7、11、13、17、19，它们确实都是这样的形式。为什么？因为模 6 余 0、2、3、4 的数要么是偶数，要么能被 3 整除，根本成不了素数，有余数 1 和 5（等价于 6k±1）才可能是素数。

于是，步长从 2 改成 6，每次只检查 6k-1 和 6k+1 两个位置，效率又提升了一倍左右：

def is_prime_6k(n: int) -> bool: if n <= 3: return n > 1 if n % 2 == 0 or n % 3 == 0: return False i = 5 while i * i <= n: if n % i == 0 or n % (i + 2) == 0: return False i += 6 return True

这里的写法非常经典，很多算法模板里都能看到。它的数学基础就是上面那个模 6 的性质，写代码时只需站在 5 这个起点，然后 i，i+2，i+6，i+8，i+12……这样以 6 为步长跳动，i 本身对应 6k-1，i+2 对应 6k+1，所有候选位置都不会漏。

2.4 试除法什么时候够用，什么时候不够用

试除法在 n 比较小的时候特别好用，比如判断 100 万以内任意一个单个数，基本就是瞬间的事。但如果要做大素数检测，比如判断一个 20 位的数字是不是素数，sqrt(n) 大约是 10 的 10 次方量级，这个循环量级是十亿，单线程跑一秒内也基本无望，这时候试除法就不太现实了。工程实践里的建议是：对于 int 范围内的单个数，试除法配上 6k±1 优化已经足够了；对于更大规模，老老实实上概率型素性检测，后面单独说。

另外一个使用试除法时容易犯的毛病：循环条件写成 i <= n / 2。看着好像缩小了范围，实际上并没有利用平方根性质，对于大数依然是线性级别，属于“以为自己优化了，其实没有”。

3. 筛法：一次算一批，从埃氏筛到线性筛

3.1 埃拉托斯特尼筛法核心思路

如果题目要求是求 [2, N] 区间内的所有素数，一个一个试除就不划算了。这时更聪明的思路是反着来：开一个长度为 N+1 的布尔数组，默认全是 True，表示“都还没被证明是合数”，然后从 2 开始，把 2 的倍数全部标记成 False，接着找下一个未被标记的数，再把它的倍数全部标记掉，以此类推。等这个流程走完，仍然为 True 的位置，就是素数。

这个筛法叫埃拉托斯特尼筛法，思路用大白话说就是“标记合数，剩下的就是素数”。关键操作是两层循环：外层从 2 到 sqrt(N) 即可，因为大于 sqrt(N) 的合数一定已经被更小的质因子标记过了；内层从 ii 开始而不是 2i 开始，因为 i 乘以小于 i 的数在更早的轮次肯定已经被标记过，这个细节能省掉大量重复标记。

def sieve_of_eratosthenes(n: int) -> list[int]: if n < 2: return [] 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(n + 1) if is_prime[i]]

这个算法的时间复杂度是 O(n log log n)，在 n 等于 100 万时基本是毫秒级的。它的空间复杂度是 O(n)，看起来是必须的，因为要记录每个数是不是素数，但这就是典型的用空间换时间，比逐个判断划算太多了。

3.2 埃氏筛里值得琢磨的两个细节：起点 i*i 和剪枝

先说起点为什么从 ii 开始。假设当前外层变量是 i，考虑 2×i 这个数，在 i=2 那轮已经标记过；3×i 这个数呢？当 i=3 那轮已经标记过。更一般地，对于任意小于 i 的因子 k，k×i 已经在更早的轮次里被处理掉了。所以只有 i 自己乘不小于 i 的数，才需要当前这轮来处理。从 ii 开始，省下的每次循环次数看似不多，但累加起来对性能影响非常明显，特别是 n 很大的时候。

剪枝指的是外层循环只需要走到 sqrt(n)，原理同试除法。一个合数 m <= n，它的最小质因子必然不超过 sqrt(m) <= sqrt(n)，所以只要把不超过 sqrt(n) 的素数倍数都筛掉，就足以覆盖所有合数。两处优化结合之后，埃氏筛在实际运行中的效率已经相当理想，对于 1000 万以内的范围，普通笔记本只需要零点几秒就能完成。

3.3 欧拉筛（线性筛）的原理：每个合数只被筛一次

埃氏筛还是有一个明显的浪费：同一个合数会被多个质因子反复标记。比如 12，既会被 2 筛到，又会被 3 筛到。这种重复标记在 n 很大时算力浪费很明显。欧拉筛的核心改进是保证每个合数只被它的最小质因子筛掉一次，这样标记次数就和合数数量线性相关，整体复杂度降到 O(n)。

实现上的关键点是一个 if 判断：当 i 能整除当前素数 p 时，就 break 掉，不再继续乘更大的素数。为啥？设 i = p × m，那么 p 是 i 的最小质因子之一，而 i 与下一个更大的素数 q 相乘得到的合数 i×q = p×m×q，这个合数的最小质因子是 p 而不是 q，所以它应该在后续 m×q 那一轮被 p 筛掉，而不是现在用 q 来筛。

def linear_sieve(n: int) -> list[int]: if n < 2: return [] 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

这个算法的精髓就在“最小质因子”这四个字上。它背后的逻辑很多初学者第一次看会觉得很绕，甚至觉得这个 break 可有可无。我建议到本地去跑一下，对比埃氏筛和线性筛实际的标记次数，比如 n=100 时，埃氏筛标记了几次，线性筛标记了几次，一对比立刻明白差距在哪。

3.4 两种筛法对比，以及应用中如何选

埃氏筛实现简单，代码简洁易读，可扩展性也强（比如后面可以派生区间筛），而线性筛稍微复杂一些，但做到了严格 O(n)，并且能顺便得到素数列表。绝大多数业务场景的 N 不超过千万量级，两者速度差别其实不算特别悬殊，用埃氏筛就足够。在竞赛环境下，如果内存敏感或者 N 特别大，会建议用线性筛。

这里要注意，所谓 O(n) 的优势在 N 比较小时根本感觉不出来，因为 log log n 这个函数增长实在太缓慢了，N 到 10 亿量级才大约 3.4。所以大多数时候选埃氏筛就够了，线性筛更重要的意义在于理解“如何避免重复工作”这一思想，这种思路放到别的算法里也很值钱。

如果你只是需要判断一个数是不是素数，就没必要先用筛法预计算一个巨大素数表再二分查找，直接单数试除反而更快。做任何选型，先想清楚输入规模和请求模式。

4. 大数据量场景下的工程化优化

4.1 当内存成为瓶颈：用分段筛解决

如果 N 是 10 亿，直接开一个长度 10 亿的布尔数组，光数组就要占用 10 亿字节，也就是大约 1GB 内存，这在很多环境下不可接受。但你要算的区间可能只是其中一小段，比如 [100亿, 100亿+1000万] 中到底有多少个素数。这个时候分段筛就派上用场了。

分段筛的思想很直观：先用普通筛法筛出 sqrt(R) 以内的所有素数，存成一个小素数表；然后针对目标区间 [L, R] 建一个布尔数组，初始全部为 True；接着用已经筛出来的每个素数 p，找到 p 在区间 [L, R] 里的第一个倍数，然后把从那里开始每隔 p 个位置的数全部标记成 False。结束后，标记为 True 的就是该区间的素数。

def segmented_sieve(L: int, R: int) -> list[int]: if L < 2: L = 2 limit = int(math.isqrt(R)) base_primes = linear_sieve(limit) is_prime = [True] * (R - L + 1) for p in base_primes: start = max(p * p, ((L + p - 1) // p) * p) for num in range(start, R + 1, p): is_prime[num - L] = False return [L + i for i in range(R - L + 1) if is_prime[i]]

可能有人疑惑 start = max(pp, ...) 这一句是为什么。前半部分 pp 的道理和埃氏筛一致，后半部分是向上取整，找大于等于 L 的第一个能被 p 整除的数，这样可以避开从 L 之前开始标记浪费工作。这个优化在区间跨度大的时候效果非常明显。

4.2 缓存局部性、内存对齐和标记位压缩

当区间长度和 N 都很大时，除了算法本身，硬件层面的优化也不可忽视。布尔数组在 Python 里是开销很大的对象列表，一个 True/False 背后是一整个对象。工程实现时常见做法是用 bytearray，用 0/1 表示，一个字节一个数；再进一步可以用 bitset，一个 bit 一个数，内存直接缩到原来的八分之一。

线性遍历时，CPU 会按缓存行方式预取数据，分段筛设计得越紧凑，缓存命中率越高。反之，如果你在内存里跳来跳去，比如频繁访问相隔非常远的索引，缓存就会反复失效，运行速度下降可能不止一个数量级。所以在大范围筛选时，尽量把数据排布得紧凑连续，即使要多做一次位运算，也是划算的。

4.3 如何并行加速筛选

如果区间里素数数量很多，分段筛天然适合多线程：把区间 [L, R] 切成若干个不相交的小段，每个线程各自处理一段，互不干扰，因为每段都只依赖于 base_primes 这个公共只读列表，没有写冲突。同步顶多发生在最后汇总结果时，开销很小。

不过要注意一个细节：每个线程处理一个段里面标记 False 的总量不一样，不同段的合数密度不同，耗时天然就不均衡。做负载均衡时可以按区间动态分配，比如每个线程跑完自己的段后去取下一个段的起点，而不是一开始就把所有段一次性锁死。这个策略在任务量波动大的场景下非常有效。并行算素数的提升虽然显著，但也别指望速度翻倍那么多，分配和同步的开销会吃掉一部分收益。

实测下来，单机多核并行处理 10 亿以内素数筛时，4 线程相对单线程的提升大约在 2.5~3 倍左右。如果你看到只提升了 1.5 倍，多半是内存带宽成了新瓶颈，不是 CPU 不够多。

5. 素数判定进阶：从试除到概率型测试

5.1 为什么需要 Miller-Rabin 这类概率算法

到了密码学里动辄 1024 位的大数，试除法已经完全不可能了。sqrt(2^1024) 约等于 2^512，这个数大到没有任何计算机能遍历完。这时候需要换一个思路，不是去检查因数是否存在，而是基于费马小定理做模幂运算，用数学性质来验证候选数字的“素数可能性”。

Miller-Rabin 算法的核心原理是：对于要判断的奇数 n，写成 n-1 = d × 2^s 的形式，然后随机选择底数 a，计算 a^d mod n，如果结果是 1 或者 n-1，就认为这一轮测试通过；否则持续平方，看是否出现 n-1。如果多次测试都通过，n 就非常可能是素数。这里的关键点是，如果 n 是合数，至少会有 3/4 的底数能揭露它不是素数，所以多测几轮错误概率会指数级下降。

import random def is_probable_prime(n: int, rounds: int = 12) -> bool: if n < 2: return False small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] for p in small_primes: if n % p == 0: return n == p d = n - 1 s = 0 while d % 2 == 0: d //= 2 s += 1 for _ in range(rounds): a = random.randint(2, n - 2) x = pow(a, d, n) if x == 1 or x == n - 1: continue for _ in range(s - 1): x = (x * x) % n if x == n - 1: break else: return False return True

我不建议在实际项目里自己实现 RSA 或大素数生成，容易在随机源和边界处理上出 bug。如果是学习目的，搞清楚这个算法的推导过程确实能加深对数论里重要定理的理解。

5.2 确定性 Miller-Rabin 的基底选择

Miller-Rabin 本质上是个概率算法，但工程实践和数论研究都已经证明：如果 n 小于某个上限，固定的几个底数就足以构成确定性测试。业界经常用的组合是 [2, 3, 5, 7, 11, 13, 17]，这个组合能精确覆盖到 341,550,071,728,321 这个数量级；要想覆盖到 2^64，用 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] 等一组特定小质数即可。

所以实际写代码时不需要随机数，直接用固定底数表做多次循环判断就行，既快又稳。很多标准库里的大素数检测用的就是这套确定性变种。对普通开发者来说，把 Miller-Rabin 和下面的说明记住就够了：它的“概率”属性在工程可控范围内完全可以做到实际上的确定。

5.3 大素数检测时的经典坑：伪素数与卡迈克尔数

有些合数会伪装成素数骗过单轮费马检测，卡迈克尔数就是典型中的典型，比如 561、1105、1729，这些数对于任何与它互质的底数 a，a^(n-1) ≡ 1 (mod n) 都成立，直接套费马小定理会误判成素数。这也是为什么在实际实用中几乎不用单纯费马检测，而是采用 Miller-Rabin 这种加强版本。

Miller-Rabin 对卡迈克尔数同样有效，因为它在平方检测环节能识别出“1 的非平凡平方根”，而这个根在真正素数里永远不会出现。所以只要轮数够多，就算某些坏数在首轮判定偏软，后续轮次也会把它揪出来。这类坑如果不是专门做算法研究，可能一辈子都遇不到，但听说过的和没听过的人在排查莫名“素数误判”时效率完全不一样。

我个人的建议：普通应用场景里，直接调用语言内置或成熟库的 is_prime 方法就行。如果非要自己写，先写清楚 unit test，把所有边界和已知卡迈克尔数全部放进去跑一遍，不然迟早会踩到隐蔽的反例。

6. 常见问题排查表与调试心得

6.1 边界条件和致命错误的速查表

求素数代码出现 bug 的概率其实不低，尤其集中在下面几个位置：

这些错误里最经典的就是把 2 漏掉，尤其是“从 3 开始加 2 跳着检查”这种优化里，如果忘了对 2 单独判断，小 n 根本测不出来，到了 2 才当场翻车。写 unit test 的时候，务必把 0、1、2、3、4、5、一个大质数、一个大合数全部覆盖到。

6.2 性能分析与进一步调优思路

遇到“筛法跑得不够快”，先做 profiling 再动手改。常见性能短板可能是：数组访问频繁但缓存命中差、内层循环体太大、内存分配过多。先看热力图再决定优化方向，优先级从高到低通常是：算法本身、内存布局、语言层面的微优化，最后才是位运算和汇编级别，别一上来就优化到最后一个阶段。

如果是超大规模，还要考虑分段筛条的宽度。段太小，外层素数表的遍历开销会被放大；段太大，内存命中率下降。不同平台上段最优宽度不一样，通常在 2^16 到 2^20 之间，具体还是要自己拉曲线实验。

6.3 为了调试顺手写出的几个小工具

调试这类算法时我经常用两个小工具。一个是对照基准：先用最简单最慢的暴力法算出 N 以内的素数表，再用优化算法算一遍，比对结果是否完全一致，这种差分测试在改动里非常靠谱。另一个是可视化间隔统计：把相邻素数之间的距离打印出来，比如 2 和 3 间隔 1，3 和 5 间隔 2，5 和 7 间隔 2，这里突然冒出来一个间隔很大的位置时，往往意味着筛选逻辑有遗漏。

另外推荐把素数表存成文件，落盘后的文件可以直接被其他程序复用，特别是那种幂等筛选、结果不变的大范围素数表，用它做各种算法实验可以省掉大量重复计算。

6.4 一个容易被忽视的经验：关键循环体里少做除法

在筛法这种高频循环里，取模运算 n % i 是很昂贵的。虽然现代 CPU 对整数除法的优化已经好很多了，但在亿级循环里，它依然是明显的热点。很多性能优化本质上是把除法换成加减法或者乘法，比如循环步长直接用 p，每次索引加 p，其实就隐含了“能被 p 整除”的判断，不需要额外再取模。这也是埃氏筛里内层写 range(ii, n+1, i) 而不是 range(ii, n+1) 然后再 if 判断的原因。

我实际调优的时候见过同事把一个筛法从两层 if 取模改成步进式遍历后，耗时直接降到原来的 60%，当时那场景印象很深。代码有时候会因为写得太“直观”而慢，适当做一点数学层面的等价变换，效果立竿见影。

我自己这些年写算法题和做工程优化，最深的体会是：求素数这件事看着基础，但它把“数学直觉”和“工程取舍”结合得非常紧密。边界情况逼你把定义吃透，筛法逼你理解重复劳动，大数检测逼你正视概率与确定性之间的平衡。建议你把每种算法的代码都亲手写一遍，再跑几个不同量级的输入做对照，这种“手感”比看十篇文章都管用。后面如果要继续深入，可以试着用筛法求区间内素数个数、做质因数分解、算欧拉函数，每条路都能打开一个新的知识面。