c++ - Sieve of Sundaram 和 Sieve of Atkin 生成素数列表的比较

Question

根据链接:http://en.wikipedia.org/wiki/Sieve_of_Sundaram，用于生成最多为 n 的素数列表的“sundaram 筛法”的运行时间为 O(n*log(n))。 .该算法是否比“阿特金筛法”更好？如果是，请详细说明其工作原理？

Answer 1

理论上:

• Sundaram 筛的算术复杂度为 O(n log n)。
• Eratosthenes 的基本筛法具有 O(n log log n) 的算术复杂度。
• Eratosthenes 筛法的优化变体具有 O(n) 的算术复杂度。
• 阿特金筛不仅具有算术复杂度，而且位复杂度为O(n/log log n)。
• 一个神奇的筛子，按顺序给出质数，需要时间 O(n/log n)。

在实践中，Sundaram 筛法太慢以至于没有人使用它，而 Atkin 筛法比优化的 Eratosthenes 变体慢(尽管它至少具有竞争力)。也许有一天阿特金或其他东西会取代埃拉托色尼，但这不太可能很快发生。 (此外，没有魔法这样的东西。)