为何更大轮基的轮式埃氏筛未能提升素数生成效率？

针对你提到的210基轮式筛法性能未达理论预期（仅略快于30基，甚至更慢）的问题，核心原因在于理论模型忽略了实际硬件与实现层面的开销，具体可拆解为以下几点：

1. 缓存效率大幅下降 #

210基轮式筛需要维护与210互质的48个余数类的标记数组（或分片），而30基仅需8个。这种分散的内存布局会导致：

• CPU缓存行的利用率极低：一次缓存加载的连续字节只能覆盖少数几个余数类的标记位，频繁触发缓存缺失（cache miss），迫使CPU等待内存数据加载，这部分延迟完全抵消了搜索空间缩小带来的收益。
• 无法利用连续内存访问的带宽优势：30基的标记操作相对集中，能更好地利用现代CPU的内存预取机制，而210基的分散访问会让预取逻辑失效。

2. 额外计算与初始化开销增加 #

• 模运算成本：210基中判断数的余数类需要执行n % 210，相比30基的n % 30，运算量更大——尤其是在编译器未针对大常数模运算做优化（如替换为位运算/乘法逆元）时，这部分开销会显著累积。
• 步长表维护：210基需要为每个质数生成对应48个余数类的标记步长，步长表的初始化时间和内存占用远高于30基，在筛法上限较小的场景下，这部分固定开销甚至会超过搜索空间缩小带来的性能提升。

3. 分支预测失效概率升高 #

210基的余数类数量更多，代码中处理不同余数类的分支逻辑（如选择对应步长、更新标记位）更复杂，CPU的分支预测器更容易出现误判，导致流水线停顿（pipeline stall）。这种硬件层面的性能损失在实际运行中，往往比理论计算的开销更显著。

4. 理论模型的理想化偏差 #

理论上的耗时比例（85.71%）是基于“每个标记操作成本完全相同”的假设，但实际场景中：

• 分散的内存访问延迟远高于连续访问，210基的单个标记操作实际成本更高；
• 仅当筛法的上限极大（如10^12及以上）时，初始化开销占比会被摊薄，210基的空间优势才可能逐渐显现，而中小范围筛法中，30基的综合性能反而更优。

内容的提问来源于stack exchange，提问作者Ξένη Γήινος