在C＃中计算素数的最快方法？

我实际上对我的问题有一个答案，但它不是并行化的，所以我对改进算法的方法感兴趣。无论如何，它可能对一些人有用。在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<int> Primes = new List<int>(); 

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

也许我可以使用多个BitArray S和BitArray.And()在一起？

来源

2008-08-27 palotasb

这是更新的代码？ – Crash893 2009-07-08 16:16:16

我知道在C＃中使用多处理的最快方式是我作为另一个问题的答案提交的代码：http://stackoverflow.com/a/18885065/549617。它可以在大约0.32秒内找到总数为10亿的素数，32位数字范围内的素数总数约为1.29秒，并且在大约3秒内达到100亿的素数**不**枚举Intel i7-2700K（3.5 GHz，四核/八线程，包括超线程）。为了提供比这更快的结果，您必须使用https://code.google.com/p/primesieve/中的C代码。 – GordonBGood 2013-12-13 09:58:20

通过交叉引用双位链表中的位数组，可以节省一些时间，以便更快地进入下一个素数。

此外，一旦你第一次打到新的素数p，剩下的第一个复合倍数将是p * p，因为之前的所有东西都已经被消除了。事实上，您只需要将列表中所有剩余的潜在素数乘以p，一旦产品超出范围（大于Until），就会停止。

那里还有一些很好的概率算法，比如Miller-Rabin测试。 The wikipedia page是一个很好的介绍。

来源

2008-08-29 09:08:27 Tyler

并行化，你不想在每次迭代时计算sqrt（直到）。您也可以假设2,3和5的倍数，并且只计算{1,5}中的N％6或{1,7,11,13,17,19,23,29}中的N％30中的N％。

您应该能够很容易地并行化因子分解算法，因为第N阶段只取决于sqrt（n）结果，所以一段时间后不会有任何冲突。但是这不是一个好的算法，因为它需要很多分割。

如果您的写入器工作包保证在读取前完成，您还应该能够并行化筛选算法。大多数作者不应该与读者发生冲突 - 至少一旦你完成了一些条目，他们应该至少在读写器上方工作N，所以你只需要偶尔读一次同步读（当N超过最后一次同步读值）。您不需要在任意数量的写入程序线程中同步布尔数组，因为不会出现写入冲突（最坏的情况是，多个线程会将同一个地址写入一个真值）。

主要问题将是确保等待写入的任何工作者已完成。在C++中，你可以使用比较和设置来切换到任何时候都在等待的worker。我不是C＃wonk，所以不知道如何去做那种语言，但Win32 InterlockedCompareExchange函数应该可用。

您也可以尝试基于演员的方法，因为这样您可以安排演员使用最低值，这可能更容易保证您读取筛的有效部分而无需锁定总线N的每个增量上。

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

来源

2008-08-27 20:52:54

@DrPizza分析只能真正帮助改进实现，并不能揭示并行执行的机会，或者提出更好的算法（除非您有其他经验，否则我很希望看到您的分析器）。

我家里只有一台核心机器，但运行了一个与您的BitArray筛网相当的Java，以及筛网的一个单一线程版本 - 在数组中保存标记素数，并使用wheel来减少搜索空间乘以5，然后使用每个标记素数以轮子的增量标记位数组。它还将存储减少到O（sqrt（N））而不是O（N），这有助于在最大的N，寻呼和带宽方面。

对于N（1e8到1e12）的中值，可以很快找到达到sqrt（N）的质数，之后您应该能够很容易地平行化CPU上的后续搜索。在我的单一核心机器上，wheel方法在28s内找到1e9的质数，而你的筛子（在将sqrt移出循环之后）需要86s - 改进是由于轮子;反转意味着你可以处理大于2^32的N，但使其变慢。代码可以找到here。在经过sqrt（N）之后，您可以并行处理来自天真筛选的结果的输出，因为在该点之后未对位阵列进行修改;但是一旦你处理的N足够大，那么数组的大小对于整数来说就太大了。

来源

2008-09-01 00:06:01

没有分析，我们不知道程序的哪个位需要优化。

如果您在一个大系统中，那么可以使用一个分析器来发现质数生成器是需要优化的部分。

分析一个循环，其中有十几个指令，通常并不值得 - 与循环体相比，探查器的开销是显着的，而改进循环的唯一方法就是改变算法做更少的迭代。因此，一旦你消除了任何昂贵的功能并且拥有一行简单代码的已知目标，那么IME最好更改算法并计时进行端到端运行，而不是尝试按指令级别改进代码剖析。

来源

2008-09-04 20:38:54

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

考虑到将元素添加到列表中可能会更便宜，因为您发现它们。

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

来源

2008-09-17 01:43:13 EvilTeach

您是否在寻找新的素数？这可能听起来很愚蠢，但是你也许可以加载某种具有已知素数的数据结构。我相信有人在那里有一个名单。找到计算新数字的现有数字可能会更容易。

您可能还会考虑微软的Parallel FX Library，以使您的现有代码可以多线程利用多核系统。通过最少的代码更改，您可以使您的循环成为多线程。

来源

2008-09-17 01:57:54

有关于埃拉托色尼的筛很好的文章：The Genuine Sieve of Eratosthenes

它在功能设置，但大多数opimization做也适用于在C＃中的程序执行。

两个最重要的优化是在P^2处开始交叉而不是2 * P，并为下一个素数使用轮子。

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

来源

2008-09-17 07:15:11

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"); 
     } 
    }

来源

2015-07-24 07:16:29 Raj

在C＃中计算素数的最快方法？

回答

相关问题