algorithm - erathosens 的筛法是生成从 1 到 N 的素数的最佳算法吗？

Question

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

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

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

编辑：就时间和空间复杂性而言最好。我刚刚告诉他们 SoE 的缺陷是空间复杂性。所以他们问我能不能做点什么。以下是采访的进行方式： 1) 实现一个算法，打印从 1 到 n 的素数 Ans: 我使用 SoE 实现 2) 这是最好的方法吗 Ans: ???

Answer 1

好吧，这取决于您所说的“最佳”是什么意思。埃拉托色尼筛很容易实现，但阿特金筛会给您带来明显更好的性能。

因此，如果“最好”意味着易于实施和理解，那么 Eratosthenes 就是要走的路。如果“最佳”意味着想要炫耀您作为数学家的技能或拥有非常快速的算法，那么阿特金就是您的最佳选择。

Answer 2

Answer 3

对于编程面试，没有:)。虽然有这个http://en.wikipedia.org/wiki/Sieve_of_Atkin并且我敢肯定那里可能有研究论文来寻求小的优化。