筛分 O(n) 中的埃拉托色尼

Question

我最近看到一篇文章，声称它可以使用高效的埃拉托色尼筛法在 O(n) 中找到所有小于 n 的素数。但是我无法看到它是如何 O(n)。

https://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/

有人可以帮忙吗？

Answer 1

Eratosthenes 的正常筛分是 O( n log log n )。

保罗·普里查德 (Paul Pritchard) 在类似于埃拉托色尼筛 (Sieve of Eratosthenes) 的筛子上做了一些工作，这些筛子在 O( n ) 甚至在 O( n / log log n ) 中运行。它们实施起来很棘手，尽管理论上的时间复杂度有所提高，但运行筛子所涉及的簿记使它们比正常的 Eratosthenes 筛子慢。

我在我的博客中讨论了一个简单版本的 Pritchard 筛。