1000 个前素数的总和给出了错误的输出

本文关键字：输出 错误 1000 | 更新日期: 2023-09-27 17:57:04

我写了一个小程序来打印出 1000 个前素数的总和，但由于某种原因我得到了错误的结果。

namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            long sum;
            sum = 0;
            int count;
            count = 0;
            for (long i = 0; count <= 1000; i++)
            {
                bool isPrime = true;
                for (long j = 2; j < i; j++)
                {
                    if (i != j && i % j == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    sum += i;
                    count++;
                }
            }
            Console.WriteLine(string.Format("{0}",sum));
            Console.ReadLine();
        }
    }
}

结果 = 预期3674995 = 3682913

1000 个前素数的总和给出了错误的输出

实现将1标识为素数，这是不正确的;这可以通过初始化isPrime来修复，如下所示。

bool isPrime = i != 1;

这3682913产生了所需的结果;但是 0 的总和也被考虑在内。

一个有效的实现只检查素数除数，直到value的平方根;请注意，所有偶数值都不是素数（唯一的例外 - 2）： 

  int count = 1000;
  List<long> primes = new List<long>(count) {
    2 }; // <- the only even prime
  for (long value = 3; primes.Count < count; value += 2) {
    long n = (long) (Math.Sqrt(value) + 0.1);
    foreach (var divisor in primes)
      if (divisor > n) {
        primes.Add(value);
        break;
      }
      else if (value % divisor == 0)
        break;
  }
  // 3682913
  Console.WriteLine(string.Format("{0}", primes.Sum()));
  Console.ReadLine();

尝试count = 1000000，你会得到7472966967499 

            long sum;
            sum = 0;
            int count;
            count = 0;
            for (long i = 0; count <= 1000; i++)
            {
                if (i == 1) continue;
                bool isPrime = true;
                for (long j = 2; j < i; j++)
                {
                    if (i != j && i % j == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    sum += i;
                    count++;
                }
            }
            Console.WriteLine(string.Format("{0}", sum));
            Console.ReadLine();
相关文章：