我最近看到一篇文章，声称可以用高效的Sieve Of Eratosthenes在O(n)内找到所有小于n的质数。然而我无法看出它是如何做到O(n)的。
https:/www.geeksforgeeks.orgsieve-eratosthenes-0n-time-complexity
谁能帮帮我？
一般的Sieve Of Eratosthenes是O(n 原木 n).
Paul Pritchard曾做过一些类似于Eratosthenes筛子的工作，这些筛子运行在O(n)，甚至在O(n 原木 n). 它们的实现很棘手，尽管理论上的时间复杂度有所提高，但运行筛子所涉及的记账使它们比普通的埃拉托斯特尼斯之筛慢。
我讨论了一个简单版本的Pritchard的筛子在 我的博客.
它是Gries和Misra(1978)筛子的一个版本，是一个O(n)筛子。 更好的描述可以在这里找到。
(外部链接) 具有线性时间复杂度的埃拉托斯特尼之筛.
有关该领域专家对这种类型的筛子的更多理论研究，请参阅Pritchard的论文。
(外部链接) 线性初数筛。A Family Tree (1987年，PDF).
Pritchard以他的子线型筛子算法和论文以及其他早期贡献而闻名。
GfG的版本使用了很多额外的内存。 CP的版本用的少一点。 两者都是 巨大 与典型的字节或位实现的SoE相比。 在10^9的情况下，它比简单的位数组单片SoE多用了60多倍的内存，而且速度也只有一半，即使使用uint32_t类型。
所以在实际应用中，它比简单的4行单片SoE要慢，这也是我们通常在 开始 在进入有趣的优化之前（分段筛、轮子等）。 如果你真的想要因子数组，那么这很有用。 这对学习和实验也很有用，虽然GfG的文章除了给出代码之外，实际上并没有做太多的事情。 CP页面确实介绍了一些历史和一些记忆速度分析。