algorithm - 计算一百万个质数

Question

我有一个问题要打印一百万个素数。我已经为此编写了一个 Java 程序。目前计算它大约需要 1.5 分钟。我认为我的解决方案效率不高。我使用了以下算法:

• 最初将 1 2 3 添加到素数列表中
• 计算要检查的号码的最后一位
• 检查数字是否为 0 、 2 或 4 或 6 或 8 然后跳过该数字
• 否则计算数字的平方根..
• 尝试除以从 2 开始的数字直到数字的平方根
• 如果数字是可整除的，则跳过该数字，否则将其添加到素数列表中

我也阅读了其他几个解决方案，但没有找到好的答案。请理想地建议计算这个的最短时间大约是多少，以及需要进行哪些更改才能使算法更有效。

Answer 1

如果您在列表中添加了 1，则您的答案已经错了:)

无论如何，Sieve of Erathosthenes是您应该开始的地方，它非常简单且非常高效。

熟悉筛子的概念及其工作原理后，您可以继续阅读 Sieve of Atkin ，这有点复杂，但显然更有效。