计算C＃素数的最快方法？
我实际上有一个问题的答案，但它没有并行化，所以我对改进算法的方法感兴趣。 无论如何，它对某些人来说可能是有用的。
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 Primes = new List(); for (int i = 2; i < Until; i++) if (PrimeBits.Get(i)) Primes.Add(i); 也许我可以将多个BitArray和BitArray.And（）一起使用？
您可以通过使用双向链表来交叉引用您的位数组来节省一些时间，这样您就可以更快地进入下一个素数。
此外，一旦你第一次碰到一个新的素数p就消除了后来的复合 – 剩下的p的第一个复合倍数将是p * p，因为之前的所有内容都已被消除。 实际上，您只需要将p乘以列表中剩余的所有剩余潜在素数，并在产品超出范围（大于Until）时立即停止。
还有一些很好的概率算法，例如Miller-Rabin测试。 维基百科页面是一个很好的介绍。
除了并行化之外，您不希望在每次迭代时计算sqrt（Until）。 您还可以假设2,3和5的倍数，并且仅计算{1,5}中的N％6或{1,7,11,13,17,19,23,29}中的N％30。
您应该能够非常容易地并行化因子分解算法，因为第N阶段仅取决于第（n）个结果，因此一段时间后不会有任何冲突。 但这不是一个好的算法，因为它需要大量的划分。
如果您有写入工作数据包，保证在读取之前完成，您还应该能够并行化筛选算法。 大多数编写者不应该与读者发生冲突 – 至少一旦你完成了一些条目，他们应该至少在阅读器上方工作N，所以你只需要偶尔进行同步读取（当N超过最后一次同步读取时）值）。 您不需要跨任意数量的写入程序线程同步bool数组，因为不会出现写入冲突（最坏的情况是，多个线程会将同一个地方写入true）。
主要问题是确保任何等待写作的工人已经完成。 在C ++中，您使用比较和设置来切换到正在等待的工作者。 我不是C＃wonk所以不知道如何使用该语言，但Win32 InterlockedCompareExchange函数应该可用。
您也可以尝试基于actor的方法，因为这样您可以安排使用最低值的actor，这可能更容易保证您正在读取筛子的有效部分而无需在每个增量上锁定总线N.
无论哪种方式，您必须确保所有工作人员在阅读之前已经超过了入口N，并且这样做的成本是在并行和串行之间进行权衡的地方。
如果没有分析，我们无法分辨程序的哪一部分需要优化。
如果您在大型系统中，那么可以使用分析器来查找素数生成器是需要优化的部分。
通常用一打左右的指令来分析循环通常不值得 – 与循环体相比，分析器的开销很大，并且改善循环的唯一方法是改变算法以减少迭代次数。 所以IME，一旦你消除了任何昂贵的function并且已经知道几行简单代码的目标，你最好改变算法和定时端到端运行，而不是试图通过指令级改进代码剖析。
@DrPizza分析只是真正有助于改进实现，它没有揭示并行执行的机会，或者建议更好的算法（除非你有其他方面的经验，在这种情况下我真的很想看你的探查器）。
我家里只有单核心机器，但运行了一个类似你的BitArray筛子的Java，以及筛子反转的单线程版本 – 将标记素数保持在一个数组中，并使用一个轮子来减少搜索空间因子为5，然后使用每个标记素数以轮的增量标记位数组。 它还将存储减少到O（sqrt（N））而不是O（N），这有助于最大N，分页和带宽。
对于N（1e8到1e12）的中等值，可以非常快速地找到高达sqrt（N）的素数，之后您应该能够非常容易地并行化在CPU上的后续搜索。 在我的单核机器上，轮子方法在28秒内找到最高1e9的质量，而你的筛子（在将环形物移出环路后）需要86s – 改进是由于轮子; 反转意味着您可以处理大于2 ^ 32的N但使其变慢。 代码可以在这里找到。 在经过sqrt（N）之后，你可以将天真筛子的结果输出并行化，因为在该点之后没有修改位数组; 但是一旦你处理N足够大，因为数组的大小对于整数来说太大了。
您还应该考虑可能的算法更改。
考虑一下，只要将元素添加到列表中就可能更便宜了。
也许预先为您的列表分配空间，可以使构建/填充更便宜。
你想找到新的素数吗？ 这可能听起来很愚蠢，但您可能能够加载某种具有已知素数的数据结构。 我相信那里有人有一个清单。 找到计算新数字的现有数字可能是一个更容易的问题。
您还可以查看Microsofts Parallel FX Library，以使您的现有代码具有multithreading以利用多核系统。 通过最少的代码更改，您可以使循环multithreading。
有一篇关于Eratosthenes筛选的非常好的文章：Eratosthenes 的真正筛选
它处于function设置中，但大多数opimization也适用于C＃中的过程实现。
两个最重要的优化是在P ^ 2而不是2 * P处开始交叉并且使用轮子用于下一个素数。
对于并发性，您可以将所有数字与P ^ 2并行处理，而不进行任何不必要的工作。
void PrimeNumber(long number) { bool IsprimeNumber = true; long value = Convert.ToInt32(Math.Sqrt(number)); if (number % 2 == 0) { IsprimeNumber = false; MessageBox.Show("No It is not a Prime NUmber"); return; } for (long i = 3; i <= value; i=i+2) { if (number % i == 0) { MessageBox.Show("It is divisible by" + i); IsprimeNumber = false; break; } } if (IsprimeNumber) { MessageBox.Show("Yes Prime NUmber"); } else { MessageBox.Show("No It is not a Prime NUmber"); } }