c# - Eratosthenes优化筛

我编写了自己的程序，使用Eratosthenes筛子从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，
  27，.. 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，7，11，13，17，19，23，29，31，37，...，83，89，97

关于c# - Eratosthenes优化筛，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38953444/