
轮式筛法通过跳过已知合数倍数来减少候选数,但性能瓶颈不在遍历素数上,而在批量标记合数的内存写操作;增大轮子虽缩小搜索空间,却无法降低主导时间复杂度的核心操作——即对每个素数 p ≤ √n 执行 primes[p² :: 2p] = False 的向量化赋值,该操作耗时占总运行时间90%以上。
轮式筛法通过利用模数结构预先排除与小质数不互质的数,显著压缩待检整数集合:例如基于30的轮子(2×3×5)仅保留8个余数类,将搜索密度降至约26.7%;而基于210的轮子(2×3×5×7)进一步压缩至约22.9%。理论上,这应带来可观加速——但实测表明,两种实现性能几乎无差异,甚至大轮子版本略慢。根本原因在于:**算法的时间支配项(dominant term)并未被轮子优化所触及。**
轮式筛法的执行流程可拆解为两个主要阶段:
轮子驱动的素数枚举(轻量级)
使用预计算的步长序列(如[4,2,4,2,4,6,2,6]或48元长数组)跳过合数候选,定位下一个待处理奇数k。这部分涉及少量整数加法、取模/位运算和条件判断,计算开销极低。即使轮子从8步扩大到48步,循环控制成本增长微乎其微(现代CPU的分支预测与缓存友好访问使其几乎常数时间)。-
核心筛除操作(重量级)
对每个识别出的素数k(满足k ≤ √n),执行:primes[k*k :: 2*k] = False
这是一次内存密集型的向量化写入:NumPy底层调用高度优化的C函数,逐块设置布尔数组中从
k²开始、步长为2k的所有位置为False。该操作的时间复杂度正比于被标记的合数个数,而这一数量由数学本质决定——与轮子大小无关。无论你用30轮还是210轮,只要k是素数,就必须筛掉其所有 ≥k²的奇倍数。实际测试中,此步骤消耗了超过90%的总运行时间(可通过line_profiler验证)。
因此,轮子优化的是“找素数”的效率,而非“筛合数”的效率。而真正耗费资源的,恰恰是后者。增大轮子虽让 k 的递增更快(例如跳过更多非素数候选),但 k 的总数(即 ≤ √n 的素数个数)本身由素数定理决定:约为 √n / ln(√n),与轮子无关。你只是更快地遍历同一组关键素数,却未减少它们引发的任何一次内存写操作。
此外,更大的轮子还引入隐性开销:
- 内存局部性下降:48元轮子数组虽小,但若未被CPU缓存完全容纳(尤其在多线程或高并发场景),频繁索引可能触发缓存未命中;
- 初始化负担:预生成长轮子列表(如210轮需存储48个字节)虽微小,但在高频调用中累积可见;
-
代码路径复杂度增加:
i = (i + 1) % 48比% 8多一次除法(尽管Numba可能优化为乘法逆元,仍非零成本)。
✅ 实践建议:
- 对于
n ≤ 10⁷,30轮(8步)是性价比最优选择——代码简洁、缓存友好、收益明确;- 追求极致性能应转向分段筛法(Segmented Sieve) 或 线性筛(Eratosthenes Linear Sieve),前者通过控制内存块大小缓解缓存压力,后者以
O(n)时间避免重复标记;- 若坚持轮式优化,可尝试动态轮子(Dynamic Wheel):对小
n用30轮,大n切换至210轮并配合手动向量化,但需实测验证收益是否覆盖工程成本。
归根结底,轮子是“聪明的跳过”,而非“魔法的加速”。在算法优化中,永远先定位真正的瓶颈——正如电动车减速比不能无限增大(否则电机转速失控、效率骤降),轮子也不能盲目扩大(否则优化点错配、收益湮没于主开销)。真正的高效,源于对计算本质的清醒认知:不是做更少的事,而是把最多时间花在最关键的事上,并让它做得最极致。










