如何进一步优化埃拉托色尼筛法

Question

我正在解决 Project Euler 问题 10，我能够使用埃拉托色尼筛法解决这个问题，但现在我想进一步优化代码。

考虑到所有大于 3 的素数都是 6k+1 或 6k-1 形式的事实，我只将数组中的这些值设置为 true，但并非所有该形式的数字都会素数，所以我必须筛选值并删除非素数，我的代码如下：

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 不是，所以是否可以只划过 25 这样的值？

Answer 1

Paul Pritchard 在轮筛方面做了很多工作，将您的 6k±1 想法扩展到更大的主轮。 Google "pritchard wheel sieve" 或查看 my blog 开始。

Answer 2

消除质数p的倍数时，只需从p * p开始。任何低于该值的 p 的倍数都将被消除，因为它具有更小的质因数。这就是您对 5 和 25 发表评论的原因。

如何进一步优化埃拉托色尼筛法

How to optimize Sieve of Eratosthenes further

c#

optimization

primes

sieve-of-eratosthenes