c# - 在 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()？

score 7 · Accepted Answer

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

此外，在第一次遇到新的素数 p 时，在消除以后的复合时 - p 剩余的第一个复合倍数将是 p*p，因为之前的所有内容都已被消除。实际上，您只需要将 p 乘以列表中所有剩余的潜在素数，只要您的乘积超出范围（大于直到）就停止。

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

score 4 · Accepted Answer

除了并行化，您不想在每次迭代时都计算 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++ 中，您可以使用 compare-and-set 切换到随时等待的 worker。我不是 C# 专家，所以不知道如何使用这种语言，但应该可以使用 Win32 InterlockedCompareExchange 函数。

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

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

score 1 · Accepted Answer

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

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

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

score 0 · Accepted Answer

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

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

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

score 0 · Accepted Answer

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

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

也许为您的列表预先分配空间会使构建/填充成本更低。

score 0 · Accepted Answer

你在寻找新的质数吗？这听起来可能很愚蠢，但您可能能够加载某种具有已知素数的数据结构。我敢肯定有人在那里有一个清单。找到计算新数字的现有数字可能要容易得多。

您还可以查看 Microsoft 的Parallel FX Library以使您现有的代码多线程以利用多核系统。通过最少的代码更改，您可以使您的 for 循环多线程。

score 0 · Accepted Answer

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

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

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

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

score -1 · Accepted Answer

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

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

8 回答 8

Related

Reference