计算一百万个素数

Question

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

• 最初将1 2 3添加到主要列表中
• 计算要检查的数字的最后一位数
• 检查数字是0,2或4还是6或8,然后跳过该数字
• 否则计算数字的平方根..
• 试图将从2开始的数字除以数字的平方根
• 如果数字是可分的,则跳过该数字,否则将其添加到主要列表中

我也读过其他几个解决方案,但我没有找到一个好的答案.请在理想情况下建议最小化计算时间,以及使算法更有效所需的更改.

Answer 1

如果您在列表中添加了1,那么您的答案已经错了:)

无论如何,Erathosthenes的筛子是你应该开始的地方,它非常简单而且效率很高.

一旦你熟悉了筛子的概念以及它们的工作原理,你就可以继续使用Atve的Sieve,这有点复杂但显然更有效率.

Answer 2

关键事项：

1. 跳过所有偶数。从 5 个开始，一次添加两个。
2. 1不是质数...
3. 通过找到所有素数的模直到数字的平方根来测试数字。除了素数，不需要测试任何东西。

Answer 3

埃拉托色尼的简单筛子就像拍板一样运行。在我的盒子上，不到一秒就可以计算出第 1,000,000 个素数：

class PrimeSieve
{
    public List<int> Primes;

    private BitArray Sieve;

    public PrimeSieve(int max)
    {
        Primes = new List<int> { 2, 3 }; // Must include at least 2, 3.
        Sieve = new BitArray(max + 1);
        foreach (var p in Primes)
            for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true;
    }

    public int Extend()
    {
        var p = Primes.Last() + 2; // Skip the even numbers.
        while (Sieve[p]) p += 2;
        for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true;
        Primes.Add(p);
        return p;
    }
}

编辑：筛选最佳地从 p^2 开始，而不是 2p，正如 Will Ness 正确指出的那样（所有低于 p^2 的复合数都将在早期迭代中标记）。