如何进一步优化埃拉托斯特尼筛网

Question

我正在解决Project Euler问题10，我可以使用Eratosthenes Sieve来完成，但现在我想进一步优化代码。

考虑到所有大于3的质数都是< code>6k 1或< code>6k-1的形式，我只将数组中的那些值设置为真，但并不是所有这种形式的数都是质数，所以我必须筛选这些值并删除非质数，我的代码如下:

public static bool[] GeneratePrimes(int bound)
    {
        bool[] isPrime = new bool[bound];
        isPrime[2] = true;
        isPrime[3] = true;

        // Taking into account that all primes greater than 2 and 3
        // Are of the form 6k+1 or 6k-1

        for (int k = 6; k < isPrime.Length; k += 6)
        {
            if (k + 1 < isPrime.Length) isPrime[k + 1] = true;
            isPrime[k - 1] = true;
        }

        // At this point we still have some numbers that aren't prime marked as prime
        // So we go over them with a sieve, also we can start at 3 for obvious reasons

        for (int i = 3; i * i <= bound; i += 2)
        {
            if (isPrime[i])
            {
                // Can this be optimized?
                for (int j = i; j * i <= bound; j++)
                    isPrime[i * j] = false;
            }
        }

        return isPrime;
    }
}

那么，我怎样才能优化我筛选出的较少数字的代码呢？例如，如果我的数字是5，那么像10、15、20这样的数字已经被划过了，但是25不是这样的吗？

Answer 1

保罗·普里查德在轮子滤网方面做了很多工作，将你的6k 1想法扩展到更大的质数轮。谷歌“普里查德轮筛”或看看我的博客开始。

Answer 2

当消去一个质数p的倍数时，你只需要从p * p开始，任何低于p的倍数都已经被消去了，因为它有一个更小的质因数。这就是你评论5和25背后的原因。