c# - 使用筛子后质数求和仍然很慢

我在下面参加了一个项目欧拉编码挑战赛，该代码给出的答案是正确的，但是我不明白为什么要花近一分钟的时间来运行它。在使用筛子之前，它以相似的时间完成。其他用户报告的时间低至毫秒。

我认为我在某个地方犯了一个基本错误...

   // The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
   // Find the sum of all the primes below two million.
   public static long Ex010()
   {
      var sum = 0L;
      var sieve = new bool[2000000];
      var primes = new List<int>(10000);

      for (int i = 2; i < sieve.Length; i++)
      {
         if (sieve[i-1])
            continue;

         var isPrime = true;
         foreach (var prime in primes)
         {
            if (i % prime == 0) {
               isPrime = false;
               break;
            }
         }

         if (isPrime) {
            primes.Add(i);
            sum += i;

            for (var x = i * 2; x < sieve.Length; x += i) {
                  sieve[x-1] = true;
            }
         }
      }

      return sum;
   }

编辑：

唯一似乎缺少的是此优化：

        if (prime > Math.Sqrt(i))
            break;

它将时间缩短到160毫秒。

编辑2：

最后单击，多次提出建议。现在是12毫秒。最终解决方案：

   public static long Ex010()
   {
      var sum = 0L;
      var sieve = new bool[2000000];

      for (int i = 2; i < sieve.Length; i++)
      {
         if (sieve[i-1])
            continue;

         sum += i;

         for (var x = i * 2; x < sieve.Length; x += i) {
            sieve[x-1] = true;
         }
      }

      return sum;
   }

最佳答案

除了筛子，您还需要进行试验划分。
布尔数组将已经告诉您一个数字是否为质数，因此您根本不需要质数表。
您也可以通过仅筛选极限的平方根来加快速度。
如果还想节省一些内存，则可以使用BitArray而不是布尔数组。

public static long Ex010()
{
    const int Limit = 2000000;
    int sqrt = (int)Math.Sqrt(Limit);
    var sum = 0L;
    var isComposite = new bool[Limit];

    for (int i = 2; i < sqrt; i++) {
        if (isComposite[i - 2])
            continue;//This number is not prime, skip

        sum += i;

        for (var x = i * i; x < isComposite.Length; x += i) {
            isComposite[x - 2] = true;
        }
    }
    //Add the remaining prime numbers
    for (int i = sqrt; i < Limit; i++) {
        if (!isComposite[i - 2]) {
            sum += i;
        }
    }
    return sum;
}

关于c# - 使用筛子后质数求和仍然很慢，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37441056/