寻找素数

引言

我最近在C# 论坛上回答了一个关于埃拉托斯特尼筛法算法的问题。提问者实际上使用蛮力实现了查找所有素数，并想知道如何更好地实现它，因为计算花费了很长时间。我通过改进算法更有效地解决了这个问题，并使用了 bool 的Array 而不是实例化的类 List，然后查阅了已发布的内容。我的算法比我找到的论文中的算法快一些，因此发布了一个替代版本。这介绍了一种使用埃拉托斯特尼筛法查找素数的更快算法。

代码

我使用一个简单的 bool Array 来表示数字，因为它应该具有最佳性能 (KISS)。它必须初始化为 true，因为算法从 true 而不是 false 开始；通过从 false 值开始，我可以略微提高性能。基本上，该算法从 2 开始，一个素数

1. 将布尔数组中索引为素数倍数的条目设置为 false。
2. 通过查找仍然为 true 的下一个最低索引值来找到下一个素数。
3. 如果找到的下一个素数小于要分析的数字的平方根，则停止，否则重复步骤 1。

停止的标准是当要检查的数字的平方根时，因为我们知道任何尚未找到的非素数都必须有大于最后一个已处理的素数的因子，或者将要处理的下一个素数乘以其自身。此算法在下面的 Run 方法中实现

  class Program
  {
    private static bool[] _numbers;
    private const int Count = 1000000000;

    static void Main(string[] args)
    {
      Console.WriteLine("Maximum number checked if prime: " + (Count - 1).ToString("n0"));
      var sw = new Stopwatch();
      sw.Start();
      Run();
      sw.Stop();
      Console.WriteLine("Milliseconds to run algorithm: " + sw.ElapsedMilliseconds);

      sw.Reset();
      sw.Start();
      Console.WriteLine("Primes: " + _numbers.Count(i => i).ToString("n0"));
      sw.Stop();
      Console.WriteLine("Milliseconds using LINQ Count: " + sw.ElapsedMilliseconds);

      sw.Reset();
      sw.Start();
      Console.WriteLine("Primes: " + _numbers.Sum(i => i ? 1 : 0).ToString("n0"));
      sw.Stop();
      Console.WriteLine("Milliseconds using LINQ Sum: " + sw.ElapsedMilliseconds);

      sw.Reset();
      sw.Start();
      Int64 sum = 0;
      for (int i = 2; i < _numbers.Count(); i++)
        if (_numbers[i]) sum += i;
      Console.WriteLine("Sum of Primes: " + sum.ToString("n0"));
      sw.Stop();
      Console.WriteLine("Milliseconds for sum of Primes: " + sw.ElapsedMilliseconds);

      Console.WriteLine("Primes:");
      for (int i = 0; i < 100; i++)
        if (_numbers[i]) Console.WriteLine("   " + i);

      Console.ReadLine();
    }

    private static void Run()
    {
      _numbers = new bool[Count];
      for (int i = 2; i < Count; i++)
        _numbers[i] = true;

      int baseCounter = 1;
      int countLimit = (int)Math.Sqrt(Count);
      while (baseCounter < countLimit)
      {
        do
        {
          baseCounter++;
          if (baseCounter == Count) return;
        } while (!_numbers[baseCounter]);

        int counter = baseCounter << 1;
        while (counter < Count)
        {
          _numbers[counter] = false;
          counter += baseCounter;
        }
      }
    }
  }

注释

• 最初，我实现了这个算法，以便它处理所有素数。将处理结束的标准设置为要分析的数字的平方根，处理时间从 40 毫秒下降到 24 毫秒。
• 我还用 BitArray 替换了 bool Array (请参阅此链接)。 这将处理时间增加了大约 50%。 但是，当使用 bool Array 的方法在 1.15 万亿到 1.2 万亿之间时，我的内存不足，而使用 BitArray 可以达到 2 万亿以上 (受限于 BitArray 的最大大小，它需要一个 int 参数)。 事实上，我可以使用布尔数组和 BitArray 处理 1 万亿个素数。 这是 BitArray 的代码

    private static void RunBitArray()
    {
      const int count = 1000000000;
      var _numbers = new BitArray(count);
      for (int i = 2; i < count; i++)
        _numbers[i] = true;

      int baseCounter = 1;
      int countLimit = (int)Math.Sqrt(count);

      while (baseCounter < countLimit)
      {
        do
        {
          baseCounter++;
          if (baseCounter == count) return;
        } while (!_numbers[baseCounter]);

        int counter = baseCounter << 1;
        while (counter < count)
        {
          _numbers[counter] = false;
          counter += baseCounter;
        }
      }
    }

• 我使用 LINQ Count 方法计算了执行计数所需的时间，它大约是查找素数时间的 80%。 使用 Sum LINQ 语句代替 Count 花费的时间略多。

历史

• 2012 年 9 月 13 日：修复了循环的结束标准，使其为计数数字的平方根。 这是因为任何剩余的非素数都必须是当前的 “baseCounter” 乘以 “baseCounter” + 2。
• 2012 年 9 月 14 日：主要重写以包含不同的选项