计算C#素数的最快方法？

Question

我实际上有一个问题的答案,但它没有并行化,所以我对改进算法的方法很感兴趣.无论如何,它对某些人来说可能是有用的.

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()一起使用？

Answer 1

您可以通过使用双向链表列交叉引用位数组来节省一些时间,这样您就可以更快地进入下一个素数.

此外,一旦你第一次碰到一个新的素数p就消除了后来的复合 - 剩下的p的第一个复合倍数将是p*p,因为之前的所有内容都已被消除.实际上,您只需要将p乘以列表中剩余的所有剩余潜在素数,并在产品超出范围(大于Until)时立即停止.

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