O(n) 中的 Eratosthenes 筛法
Sieve Of Eratosthenes in O(n)
我最近看到一篇文章声称它可以使用高效的埃拉托色尼筛法在 O(n) 中找到所有小于 n 的素数。但是我看不到它是 O(n)。
https://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/
有人可以帮忙吗？
正常的埃拉托色尼筛法是 O(n log log n).
Paul Pritchard 在 O(n) 甚至 O( n/日志日志n)。它们实施起来很棘手，尽管理论上时间复杂度有所提高，但 运行 筛分过程中涉及的簿记工作使它们比普通的埃拉托色尼筛分法慢。
我在 my blog 讨论了普里查德筛法的简单版本。
它是 Gries 和 Misra (1978) 筛的一个版本，它是一个 O(n) 筛。可以在这里找到更好的描述：
（外部 link）Sieve of Eratosthenes Having Linear Time Complexity.
要从该领域的专家那里更深入地了解这种筛子，请参阅 Pritchard 的论文：
（外部 link）Linear Prime-Number Sieves: A Family Tree (1987, PDF).
Pritchard 以其次线性筛算法和论文以及其他早期贡献而闻名。
GfG 的版本使用了很多额外的内存。 CP 的版本用得少一点。与 SoE 的典型字节或位实现相比，两者都巨大。在 10^9 时，它使用的内存比简单的位阵列单片 SoE 多 60 倍以上，速度也减半，即使在使用 uint32_t 类型时也是如此。
因此在实践中它比简单的 4 线单片 SoE 慢，这通常是我们 开始 在进入有趣的优化（分段筛、轮等）之前的地方。 ).如果你真的想要因子数组，那很有用。它对于学习和实验也很有用，尽管 GfG 文章除了提供代码之外实际上并没有做太多事情。 CP 页面确实回顾了一些历史和一些 memory/speed 分析。
我最近看到一篇文章声称它可以使用高效的埃拉托色尼筛法在 O(n) 中找到所有小于 n 的素数。但是我看不到它是 O(n)。
https://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/
有人可以帮忙吗？
正常的埃拉托色尼筛法是 O(n log log n).
Paul Pritchard 在 O(n) 甚至 O( n/日志日志n)。它们实施起来很棘手，尽管理论上时间复杂度有所提高，但 运行 筛分过程中涉及的簿记工作使它们比普通的埃拉托色尼筛分法慢。
我在 my blog 讨论了普里查德筛法的简单版本。
它是 Gries 和 Misra (1978) 筛的一个版本，它是一个 O(n) 筛。可以在这里找到更好的描述：
（外部 link）Sieve of Eratosthenes Having Linear Time Complexity.
要从该领域的专家那里更深入地了解这种筛子，请参阅 Pritchard 的论文：
（外部 link）Linear Prime-Number Sieves: A Family Tree (1987, PDF).
Pritchard 以其次线性筛算法和论文以及其他早期贡献而闻名。
GfG 的版本使用了很多额外的内存。 CP 的版本用得少一点。与 SoE 的典型字节或位实现相比，两者都巨大。在 10^9 时，它使用的内存比简单的位阵列单片 SoE 多 60 倍以上，速度也减半，即使在使用 uint32_t 类型时也是如此。
因此在实践中它比简单的 4 线单片 SoE 慢，这通常是我们 开始 在进入有趣的优化（分段筛、轮等）之前的地方。 ).如果你真的想要因子数组，那很有用。它对于学习和实验也很有用，尽管 GfG 文章除了提供代码之外实际上并没有做太多事情。 CP 页面确实回顾了一些历史和一些 memory/speed 分析。