
轮式筛法通过跳过已知合数倍数来缩小搜索空间,但实验表明增大轮子(如从30到210)几乎不提升性能;根本原因在于:算法耗时主体是标记合数的内存写操作,而轮子仅优化了“找质数”的次要环节。
轮式筛法通过跳过已知合数倍数来缩小搜索空间,但实验表明增大轮子(如从30到210)几乎不提升性能;根本原因在于:算法耗时主体是标记合数的内存写操作,而轮子仅优化了“找质数”的次要环节。
在素数筛法的工程实践中,一个常见直觉是:“轮子越大,跳过的合数越多,检查的候选数越少,速度理应越快”。你正确推导出:基于模30的轮子只需检查8/30 ≈ 26.7%的数,而模210轮子进一步压缩至48/210 ≈ 22.9%,理论搜索空间缩减约14%。然而实测结果却令人困惑——prime_wheel_sieve4_1(210轮)与prime_wheel_sieve3(30轮)运行时间几乎持平,甚至波动在±1%以内。这并非代码缺陷或测量误差,而是触及了算法性能分析的核心原则:优化必须作用于真正的时间支配项(time-dominating operation)。
我们来拆解轮式筛法的执行开销:
# 关键操作分解(以 prime_wheel_sieve4_1 为例)
primes = np.ones(n + 1, dtype=np.uint8) # O(n) 初始化,仅一次
primes[:2] = False # O(1)
for square, step in ((4,2), (9,6), (25,10), (49,14)):
primes[square::step] = False # 四次切片赋值,O(n/2 + n/6 + n/10 + n/14) ≈ O(n)
k = 11; lim = int(sqrt(n))
while k 95%
k += wheel[i]; i = (i+1) % 48 # 轮子步进:极轻量计算
✅ 轮子优化的是
if primes[k]:这一判断路径:它减少了需进入内层标记逻辑的k的数量(例如,210轮下检查约22.9%的数,30轮下为26.7%)。但该判断本身是单次内存读取(primes[k]),成本极低(纳秒级)。❌ 轮子完全未改变主导开销:`primes[k2 :: 2*k] = False
**。对每个质数k ≤ √n,此操作需执行约n/(2k)次内存写入。其总成本为: [ sum_{substack{k ext{ prime} \ k leq sqrt{n}}} rac{n}{2k} pprox rac{n}{2} cdot sum_{k leq sqrt{n}} rac{1}{k} sim rac{n}{2} cdot ln ln n ] 这一求和项由质数分布决定,**与轮子大小无关**——无论你用30轮还是210轮,只要k是质数,就必须对它的所有 ≥k² 的倍数做标记。轮子只是帮你更快地 *到达*k,但k` 的集合(即 ≤√n 的所有质数)是固定的,标记工作量完全不变。-
⚠️ 轮子反而引入微小开销:
- 更大的轮子(如48元素数组)导致
wheel[i]查表访问的缓存局部性略差; -
i = (i+1) % 48比% 8多一次除法(尽管Numba可能优化为乘法逆元,但仍非零成本); - 预处理的初始质数更多(需手动筛掉2,3,5,7而非仅2,3,5),增加常数项。
- 更大的轮子(如48元素数组)导致
? 类比理解:想象一支工程队修建一条100公里公路。轮子优化相当于改进了勘测员寻找“适合打地基的位置”的效率——从每公里勘测15个点减少到10个点。但修路耗时99%花在混凝土浇筑和压实上,而这完全取决于公路总长和地质条件,与勘测点密度无关。再快的勘测,也无法让浇筑变快。
因此,追求更大轮子是典型的“优化错位”(premature optimization)。若真要提升筛法性能,应聚焦:
- 使用更高效的数据结构(如
bitarray替代np.ndarray[uint8],节省7/8内存带宽); - 并行化标记阶段(
primes[k**2 :: 2*k]可分段并行); - 采用分段筛(Segmented Sieve)突破内存限制,提升缓存命中率;
- 对于超大
n,切换至线性筛法(如欧拉筛),将时间复杂度从O(n log log n)降至O(n)。
轮子的价值不在速度,而在概念清晰性与可扩展性:它将“哪些数可能为质数”这一数论结构(即与基础模数互质的剩余类)显式编码,是连接初等数论与高效算法的优雅桥梁——只是这座桥,不负责承载主要车流。











