为何理论时间复杂度更优的Sieve of Atkins实际运行速度始终慢于Sieve of Eratosthenes

实际运行速度结论 #

在绝大多数常见场景（包括教学实现、目标素数范围<10^12、常规内存限制）下，Sieve of Eratosthenes（埃氏筛）的运行速度优于Sieve of Atkins（阿特金斯筛）

• 用户使用的GeeksForGeeks教学实现测试结果符合普遍规律
• 仅在极端优化、目标素数范围超过10^12且硬件支持特定指令集的小众场景下，优化后的阿特金斯筛变种才可能反超，这类场景在普通开发或测试中极少出现

阿特金斯筛理论优势无法落地的核心原因 #

• 渐近复杂度的局限性：阿特金斯筛的理论时间复杂度（O(n / log log n)）是渐近意义上的，仅在n趋近于无穷大时才会体现优势；但实际测试的n（通常<10^9）远未达到“渐近临界值”，常数项的影响远大于渐近复杂度的差异
• 内存访问模式的劣势：阿特金斯筛的核心操作是基于x、y的组合生成离散数值（如4x²+y²、3x²±y²），对应的内存位置是随机分布的，会导致大量缓存未命中（cache miss）；而埃氏筛是连续标记素数的倍数，内存访问是顺序或块式的，对CPU缓存极度友好
• 朴素实现的优化缺失：教学用的阿特金斯筛实现未包含关键优化步骤：
  • 模60余数过滤（仅保留x、y满足特定模运算的组合，大幅减少循环次数）
  • 预计算有效组合（避免无效的x、y遍历）
  • 位向量压缩（减少内存占用，提升缓存利用率）
• 维基百科结论的前提限制：维基百科提及的阿特金斯筛更快的结论，是基于极端优化的工业级实现（而非教学实现），这类实现通常需要配合分段内存布局、SIMD指令集等定制化优化，且仅在超大素数范围（>10^12）下才会显现优势

注：阿特金斯筛的原始设计目标是解决超大素数范围的生成问题，而非常规场景下的通用素数查找

内容的提问来源于stack exchange，提问作者CrashMan123