c# - Eratosthenes 优化筛

Question

我编写了自己的程序，使用埃拉托色尼筛法从 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);
    }
}

Answer 1

我已经运行了您的例程 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, 11, 13, 17, 19, 23, 29, 31, 37, ..., 83, 89, 97