关于.net：在C＃中计算素数的最快方法？

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

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

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

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

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

除了并行化，您不想每次迭代都计算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 ++中，您将使用"比较并设置"切换到随时等待的工作程序。我不是C＃使用者，所以不知道该用哪种语言，但是Win32 InterlockedCompareExchange函数应该可用。

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

无论哪种方式，您都必须在阅读之前确保所有工作人员都高于条目N，而这样做的代价是要在并行和串行之间进行权衡。

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

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

分析其中包含十几条指令的循环通常是不值得的-与循环主体相比，探查器的开销很可观，而改善循环的唯一方法是减小循环的唯一方法是更改??算法以减少迭代次数。因此，IME一旦消除了任何昂贵的功能，并有了几行简单代码的已知目标，那么与尝试按指令级别改进代码相比，最好改变算法并定时进行端到端运行分析。

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

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

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

对于并发性，您可以并行处理直到P ^ 2的所有数字，而不进行任何不必要的工作。

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

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

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

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

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

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

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

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