algorithm - 埃拉托色尼筛法是生成从 1 到 N 的素数的最佳算法吗？

Question

我在一次采访中被问到这个问题。 我使用埃拉托色尼筛法概念和数组实现了一种算法。

有没有更好的方法来解决这个问题 对于那些不知道筛子的人，这是链接:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

编辑:在时间和空间复杂性方面最好。 我只是告诉他们 SoE 的缺陷是空间复杂性。 所以他们问我是否可以做点什么。 以下是采访的过程: 1) 实现一个打印从 1 到 n 的素数的算法 答:我使用 SoE 实现 2)这是最好的方法吗 答:???

Answer 1

好吧，这取决于您所说的“最佳”是什么意思。 Eratosthenes 筛法很容易实现，但是 Sieve of Atkin会给你显着更好的性能。

因此，如果“最佳”意味着易于实现和理解，那么埃拉托色尼就是最佳选择。如果“最好”意味着想要展示您作为数学家的技能或拥有非常快的算法，那么阿特金就是您的不二之选。