埃拉托色尼优化筛法

本文关键字：筛法 优化 埃拉托 | 更新日期: 2023-09-27 18:02:22

我编写了自己的程序，使用埃拉托色尼筛法从2 - n中查找素数。有什么方法我可以实现一个更有效的方式来删除合数?

项目链接:https://github.com/Gurran/Sieve-of-Eratosthenes

class Program
{
    static void Main()
    {
        int max;
        Console.Write("Enter max number: ");
        max = int.Parse(Console.ReadLine());
        FindPrimes(max);
        Console.ReadLine();
    }
    // Prints numbers.
    public static void PrintMap(List<int> List)
    {
        for (int i = 0; i < List.Count; i++)
        {
            if (i % 10 == 0)
                Console.WriteLine();
            Console.Write(List.ElementAt(i) + ", ");
        }
    }
    // Generates list containing 2 - max
    // Removes non-primes
    // Calls PrintMap method
    public static void FindPrimes(int max)
    {
        int x = 2;
        List<int> NrRange = new List<int>();
        for (int i = 2; i < max; i++)
            NrRange.Add(i);
        for (int i = 0; i < NrRange.Count; i++)
            for (int j = x; j < NrRange.Count; j++)
                if (NrRange.ElementAt(j) % x == 0)
                    NrRange.RemoveAt(j);
            x++;
        PrintMap(NrRange);
    }
}

埃拉托色尼优化筛法

我已经运行了你的例行程序FindPrimes(100)，我已经错了结果:

2, 3, 5, 7, 9 , 11日,13日, 15 , 17日,19日, 21 , 23日, 25 , , . .95， 97， 99

让我们用另一种方式来写:

// If we put "FindPrimes", let's return them: List<int> instead of void
public static List<int> FindPrimes(int max) {
  if (max < 2)
    return new List<int>();
  // Try avoid explict adding .Add(), but generating
  List<int> result = Enumerable
    .Range(2, max - 1)
    .ToList();
  // sieving composite numbers out the initial list
  for (int i = 1; i < result.Count; ++i) {
    int prime = result[i - 1];
    // removing all numbers that can be divided by prime found
    // when removing we should loop backward
    for (int j = result.Count - 1; j > i; --j)
      if (result[j] % prime == 0)
        result.RemoveAt(j); 
  }
  return result;
}

测试
 Console.Write(String.Join(", ", FindPrimes(100)));

结果:

2、3、5、7、11、13、17日,19日,23日,29日,31日,37岁,…， 83, 89, 97

您可以在c#中对Eratosthenes的基本筛分进行许多优化，这对于更大的范围(例如数十亿到数万亿)变得非常重要，包括分割技术以减少内存使用并增加缓存位置，多处理，轮分解以减少复合数筛选的数量，以及筛选复合数的模式以减少筛选循环的复杂性，我在以下回答中介绍了其中的许多内容:如何使用多线程c#实现埃拉托色尼筛子?这些技术将每个复合号码的调用次数减少到远低于每个复合号码的理想比率(约为筛到十亿范围的四分之一)，因为消除了轮上的复合因素，并且时间在使用的核心数量之间平均分配。

有一种通过另一种模式过滤复合材料的替代方法，它将速度提高了大约两倍，但我还没有发表。它更快，因为它降低了复杂性，不需要对最内层的筛选循环进行表查找。

使用另一种语言，如C/c++、Rust、Nim、Haskell等，这些语言可以生成更高效的机器码，并且除了所有其他技术之外，还允许主要展开合数筛选循环(s)，速度更快，因为它可以将每个合数筛选所需的时间从现代桌面CPU的10个时钟周期减少到一个时钟周期以上。因此，在3.5 GHz/4核CPU(如我使用的Intel i7-2700)上，将合数剔除到十亿范围所需的时间可以减少到大约63毫秒。如果您想要更多的启动数计数，时间当然会增加。

所使用的技术类似于Kim Walich的开源c++ primesieve (https://primesieve.org)，除了新的模式，它将使它稍微快一些，因为增加了车轮分解和稍微不那么复杂，但你可能会发现他的源代码很难阅读和理解(你可能会发现我的代码很难理解车轮分解模式，除非你是一个数学家)。然而，你应该能够运行他的程序，看看什么是可能的。

正如所指出的，你的程序不是一个真正的埃拉托色尼筛子，而是一个低效的分法审判版本(当被纠正时)。因为你可能不会欣赏我的其他解决方案的复杂性(先走后跑)，请看看c#无界筛的最后一个:rosettacode.org/Sieve_of_Eratosthenes#Unbounded，它在功能上与您的代码相同，但使用埃拉托色尼的分段筛，并进行位打包(每个奇数试数1位)，使用只有奇数的数字，因为2是唯一的偶数素数。

我所链接的任何程序都将比你的程序快很多很多倍，即使是在固定的情况下，除了非常小的范围。

我的代码:https://github.com/ktprime/ktprime/blob/master/PrimeNumber.cpp基准流程:

                          i3-350M,i5-3470,i7-7500u,i7-6700,r7-1700
Pi(0,    1e10) = 455052511    3.10   1.84    1.55     1.32    1.65
Pi(1e11, 1e10) = 394050419    4.35   2.50    2.02     1.78    2.00
Pi(1e12, 1e10) = 361840208    5.30   3.00    2.40     2.04    2.25
Pi(1e13, 1e10) = 334067230    6.52   3.50    2.85     2.39    2.67
Pi(1e14, 1e10) = 310208140    7.90   4.20    3.50     2.87    3.20
Pi(1e15, 1e10) = 289531946    9.90   5.10    4.32     3.49    3.91
Pi(1e16, 1e10) = 271425366    11.7   6.10    5.11     4.12    4.73
Pi(1e17, 1e10) = 255481287    13.9   7.09    5.95     4.84    5.63
Pi(1e18, 1e10) = 241272176    17.2   8.58    7.17     5.82    6.88
Pi(1e19, 1e10) = 228568014    24.0   11.6    9.86     8.00    9.50
Pi(0-1e9,10^9) = 22537866     8.15   4.28    3.92     3.02    3.64
Pi(1e18, 10^6) = 24280        0.65   0.46    0.34     0.48    0.60
Pi(1e18, 10^8) = 2414886      1.30   0.81    0.70     0.60    0.70
Pi(1e18, 10^9) = 24217085     3.50   1.80    1.58     1.26    1.50
Pi(0,    1e12) = 37607912018  500    270     224      200     220
Pi(1e14, 1e12) = 31016203073  790    420     354      295     320
Pi(1e16, 1e12) = 27143405794  1160   600     512      420     485
Pi(1e18, 1e12) = 24127637783  1500   760     622      520     640
Pi(1e19, 1e12) = 22857444126  1700   830     702      600     665
相关文章：