寻找素数

• 下载 Primes.zip - 3.8 KB

引言

这是使用埃拉托斯特尼筛法查找质数的实现的一个更快且更节省空间的变体。

背景

我们知道所有大于 2 的偶数都不是质数，因此在筛法过程中先验地将其移除。

使用代码

与克利福德·纳尔逊的版本一样，我使用了简单的布尔数组来表示数字。但是，数字并没有直接表示。索引 n 处的布尔值表示数字 2n+1（对于 n > 0）。因此，数组可以缩小到之前版本的一半大小。我的计时显示，这大约快了两倍。

质数高达	旧版本	新版本
2,000,000	7.7 毫秒	3.14 毫秒
4,000,000	16.41 毫秒	7.00 毫秒

附件中的文件包含用于计算时序的两种版本的代码。

以下代码只是新的实现。只需将其复制并粘贴到控制台应用程序中即可

  class Program
  {
    private const int repeats = 1000;  // to get more significant timing
    private const int rawCount = 2000000;
    private const int initStart = 1;
    private const int count = 1 + (rawCount - 1) / 2; // 1+ because rawCount-1 just might be prime
    private static readonly int countLimit = (((int)Math.Sqrt(rawCount)) - 1) / 2;
    private static bool[] _numbers = new bool[count];

    static void Main(string[] args)
    {
      var sw = new System.Diagnostics.Stopwatch();
      for (int j = 0; j < repeats; j++)
      {
        // I excluded initializing the _numbers array from the timing.
        for (int i = initStart; i < count; i++)
        {
          _numbers[i] = true;
        }
        sw.Start();
        Run2();
        sw.Stop();
      }
      Console.WriteLine("Milliseconds/run: {0:F2}", sw.ElapsedMilliseconds/(double)repeats);
      // The 1+ of the count is because 2 is assumed to be prime and is not represented in the array.
      Console.WriteLine((1 + _numbers.Count(i => i)) + " primes < " + rawCount);
      Console.ReadLine();
    }

    private static void Run2()
    {
      int baseCounter = 0;
      int increment;
      int index;
      while (baseCounter < countLimit)
      {
        do
        {
          baseCounter++;
          if (baseCounter == count)
            return;
        } while (!_numbers[baseCounter]);
        increment = (baseCounter << 1) + 1;
        index = baseCounter + increment;
        while (index < count)
        {
          _numbers[index] = false;
          index += increment;
        }
      }
    }
  }

关注点

我想知道是否有可能假设筛法中的其他小质因数，并进一步减小数组的大小？我确信这是不可能的，因为存在差值为 2 的质数对（例如 11 和 13），因此对筛法数组的进一步压缩是不可能的（至少对于埃拉托斯特尼筛法而言）。

奇怪的是，当筛法数组的大小超过约 6MB 时，两种版本都表现出明显的减慢。

这种筛法的改进并非全新！ 在 Code Project 中搜索“Eratosthenes”，您会找到许多实现。其中一些（可能大部分）使用这种类型的优化。

还有其他更快的方法来按顺序查找质数，尤其是在处理大数值时，请参阅 阿特金筛法 [^]。

历史

2012/9/13 - 首次发布替代方案。