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

StackOverflow https://stackoverflow.com/questions/30877

题

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

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沙 BitArray.And() 他们在一起？

有帮助吗？

解决方案

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

另外，在消除后面的复合时，一旦您第一次遇到新的质数 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 阶段仅取决于第 sqrt(n) 个结果，因此一段时间后不会出现任何冲突。但这不是一个好的算法，因为它需要大量除法。

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

主要问题是确保任何正在等待写入的工作人员都已完成。在 C++ 中，您可以使用比较并设置来切换到随时等待的工作程序。我不是 C# 专家，所以不知道如何使用该语言，但 Win32 InterlockedCompareExchange 函数应该可用。

您还可以尝试基于参与者的方法，因为这样您可以安排参与者使用最低值，这可能更容易保证您正在读取筛子的有效部分，而不必在每个增量上锁定总线N。

无论哪种方式，您都必须确保所有工作人员在阅读之前都已获得以上条目 N，而这样做的成本就是在并行和串行之间进行权衡的地方。

如果没有分析，我们就无法判断程序的哪一部分需要优化。

如果您在一个大型系统中，那么人们会使用分析器来查找素数生成器是需要优化的部分。

对包含十几条指令的循环进行分析通常不值得 - 与循环体相比，分析器的开销非常大，并且改进如此小的循环的唯一方法是更改​​算法以进行更少的迭代。因此，IME，一旦您消除了任何昂贵的函数并且有了几行简单代码的已知目标，您最好更改算法并安排端到端运行，而不是尝试通过指令级别改进代码分析。

@DrPizza 分析仅真正有助于改进实现，它不会揭示并行执行的机会，或建议更好的算法（除非您有其他方面的经验，在这种情况下我真的很想看看您的分析器）。

我家里只有单核机器，但运行了相当于 BitArray 筛子的 Java 版本，以及筛子反转的单线程版本 - 将标记素数保存在数组中，并使用 车轮 将搜索空间减少五分之一，然后使用每个标记素数以轮的增量标记位数组。它还将存储减少到 O(sqrt(N)) 而不是 O(N)，这在最大 N、分页和带宽方面都有帮助。

对于 N 的中等值（1e8 到 1e12），可以很快找到 sqrt(N) 以内的素数，之后您应该能够非常轻松地在 CPU 上并行执行后续搜索。在我的单核机器上，轮子方法在 28 秒内找到 1e9 以内的素数，而你的筛子（将 sqrt 移出循环后）需要 86 秒 - 改进是由于轮子；反转意味着您可以处理大于 2^32 的 N，但速度会变慢。代码可以找到 这里. 。在经过 sqrt(N) 之后，您也可以并行化朴素筛结果的输出，因为在该点之后位数组不会被修改；但是一旦你处理的 N 足够大，数组大小对于整数来说就太大了。

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

考虑一下，当您找到元素时，将它们简单地添加到列表中可能会更便宜。

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

你想寻找新的素数吗？这可能听起来很愚蠢，但您也许能够加载某种具有已知素数的数据结构。我确信有人有一份清单。找到现有数字来计算新数字可能是一个更容易的问题。

您也可以看看微软 并行FX库 使您现有的代码成为多线程以利用多核系统。通过最少的代码更改，您可以使 for 循环成为多线程。

有一篇关于埃拉托斯特尼筛法的非常好的文章： 真正的埃拉托色尼筛子

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

两个最重要的优化是从 P^2 而不是 2*P 开始划掉，并使用轮子来计算下一个素数。

对于并发性，您可以与 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");
        }
    }
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top