我实际上对我的问题有一个答案，但是它没有并行化，因此我对改善算法的方法很感兴趣。无论如何，对于某些人来说，它可能仍然是有用的。

int Until = 20000000;
BitArray PrimeBits = new BitArray(Until, true);

/*
 * Sieve of Eratosthenes
 * PrimeBits is a simple BitArray where all bit is an integer
 * and we mark composite numbers as false
 */

PrimeBits.Set(0, false); // You don't actually need this, just
PrimeBits.Set(1, false); // remindig you that 2 is the smallest prime

for (int P = 2; P < (int)Math.Sqrt(Until) + 1; P++)
    if (PrimeBits.Get(P))
        // These are going to be the multiples of P if it is a prime
        for (int PMultiply = P * 2; PMultiply < Until; PMultiply += P)
            PrimeBits.Set(PMultiply, false);

// We use this to store the actual prime numbers
List<int> Primes = new List<int>();

for (int i = 2; i < Until; i++)
    if (PrimeBits.Get(i))
        Primes.Add(i);

也许我可以同时使用多个BitArrays和BitArray.And()吗？

解决方案

回答

除了并行化，我们不想在每次迭代中都计算sqrt(Until)。我们还可以假设2、3和5的倍数，并且仅计算{1,5}中的N％6或者{1,7,11,13,17,19,23,29}中的N％30。

我们应该能够非常轻松地并行化分解算法，因为第N个阶段仅取决于第sqrt(n)个结果，因此一段时间后不会出现任何冲突。但这不是一个好的算法，因为它需要大量划分。

如果我们有保证可以在读取之前完成的写入器工作包，那么我们还应该能够并行化筛子算法。通常，至少在我们完成一些输入之后，编写者就不应与读取器发生冲突，它们应该在读取器之上至少工作N个，因此我们仅需要偶尔进行同步读取(当N超过最后一个同步读取值时) )。我们不需要在任何数量的写程序线程上同步bool数组，因为不会发生写冲突(最坏的情况是，多个线程将在同一位置写一个true)。

主要问题是确保等待写入的所有工作人员都已完成。在C ++中，我们将使用比较设置来切换到随时等待的工作程序。我不是Cwonk，所以不知道该用哪种语言，但是Win32 InterlockedCompareExchange函数应该可用。

我们也可以尝试使用基于actor的方法，因为这样可以安排使用最低值的actor，这可能更容易确保我们正在读取筛网的有效部分，而不必在每次递增时都锁定总线。 N.

无论哪种方式，我们都必须确保所有工作人员在阅读条目N之前都已达到该条件，并且这样做的代价是要在并行与串行之间进行权衡。

回答

通过用双向链接列表交叉引用位数组，可以节省一些时间，因此我们可以更快地前进到下一个素数。

同样，在我们第一次击中新质数p时消除以后的合成时，剩余的p的第一个合成倍数将为p * p，因为之前的所有内容都已被消除。实际上，我们只需要将p乘以列表中剩余的所有剩余质数即可，只要乘积超出范围(大于直到)就停止。

还有一些好的概率算法，例如Miller-Rabin测试。维基百科页面是一个很好的介绍。

回答

@DrPizza Profiling只能真正帮助改善实现，它不会揭示并行执行的机会，也不能建议更好的算法(除非我们有其他经验，在这种情况下，我很想看看探查器)。

我家里只有单核计算机，但运行的Java等效于BitArray筛子，并且筛子的反转的单线程版本将标记质数保存在数组中，并使用滚轮将搜索空间减少了一个。系数为5，然后使用每个标记质数以轮的增量标记位阵列。它还将存储减少为O(sqrt(N))而不是O(N)，这在最大的N，分页和带宽方面均有所帮助。

对于N的中等值(1e8到1e12)，可以很快找到sqrt(N)的质数，此后，我们应该能够很容易地并行化CPU上的后续搜索。在我的单核机器上，滚轮方法可以在28s内找到最高达1e9的质子，而筛子(将sqrt移出环路后)需要86s的改进是由于滚轮；反转意味着我们可以处理大于2 ^ 32的N，但会使其变慢。代码可以在这里找到。经过sqrt(N)后，我们也可以并行处理朴素筛子的结果输出，因为在此之后，位数组未修改；但是一旦我们处理了足够大的N，那么对于int而言，数组大小就太大了。

回答

Without profiling we cannot tell which bit of the program needs optimizing.

如果我们使用的是大型系统，则可以使用分析器来发现素数生成器是需要优化的部分。

与探查器主体相比，分析器的开销比探查器的开销大得多，通常不值得在其中包含十几条指令的情况下进行探查，而改善探查器的唯一方法就是改变算法以减少迭代次数。因此，IME一旦消除了所有昂贵的功能，并有了几行简单代码的已知目标，那么与尝试按指令级别改进代码相比，最好改变算法并确定端到端运行的时间分析。

回答

我们还应该考虑算法的可能更改。

考虑到将它们简单地添加到列表中可能会更便宜。

也许为列表预先分配空间将使构建/填充便宜。

回答

我们是否正在寻找新的素数？这听起来可能很愚蠢，但是我们可能能够加载已知素数的某种数据结构。我敢肯定有人在那里有一个清单。找到计算新数字的现有数字可能会容易得多。

我们可能还会查看Microsoft的Parallel FX Library，使现有代码成为多线程，以利用多核系统。通过最少的代码更改，我们可以使for循环成为多线程的。

回答

一篇关于Eratosthenes筛子的好文章：Eratosthenes的真正筛子

它处于功能设置中，但是大多数优化的确也适用于C＃中的过程实现。

两个最重要的优化是从P ^ 2而不是2 * P开始舍去，并使用转轮表示下一个质数。

对于并发，我们可以并行处理所有数字直到P ^ 2与P并行，而无需执行任何不必要的工作。