最快的计算在C＃中素数的方法吗？ [英] Fastest way to calculate primes in C#?

问题描述

其实，我有一个回答我的问题，但它不是并行，所以我很感兴趣，如何改善算法。反正是，对于某些人来说可能是有用的。

I actually have an answer to my question but it is not parallelized so I am interested in ways to improve the algorithm. Anyway it might be useful as-is for some people.

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 和<一href="http://msdn.microsoft.com/en-us/library/system.collections.bitarray.and.aspx">BitArray.And()他们在一起吗？

推荐答案

您可能会节省一些时间通过交叉引用您的位阵列，双向链表，这样你就可以更快速地前进到下一个素数。

You might save some time by cross-referencing your bit array with a doubly-linked list, so you can more quickly advance to the next prime.

此外，在消除后复合材料一旦你达到一个新的素数p的第一次 - P其余将是p * p的第一个复合多，因为一切都在这之前已经被淘汰。其实，你只需要通过所有正在离开后，在列表中剩余的潜在质数相乘磷，只要你的产品超出范围（比之前大）停止。

Also, in eliminating later composites once you hit a new prime p for the first time - the first composite multiple of p remaining will be p*p, since everything before that has already been eliminated. In fact, you only need to multiply p by all the remaining potential primes that are left after it in the list, stopping as soon as your product is out of range (larger than Until).

也有一些很好的概率算法那里，如米勒 - 拉宾测试。 维基百科页面是一个很好的介绍。

There are also some good probabilistic algorithms out there, such as the Miller-Rabin test. The wikipedia page is a good introduction.

这篇关于最快的计算在C＃中素数的方法吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！