什么是找到素数总和的更有效方法？

Question

我正在开发一个程序，该程序跟踪将所有素数的总和达到某个数字所花费的时间，并试图找到获得该值的最有效方法，因为我有秒表 (System.Diagnostics) 跟踪需要多长时间。目前，我可以使用以下代码在大约 33-34 秒内求出所有不超过 40,000 的素数之和：

private void ListThePrimes()
        {
            prime = false;
            while (primes < 30000)
            {
                for (int i = 2; i < n; i++)
                {

                    output = n % i;
                    if (output == 0)
                    {
                        primeNum = i;
                        prime = false;
                        break;
                    }
                    else
                    {
                        prime = true;
                    }
                }
                if (prime == true)
                {
                    sum += primeNum;
                    primes++;
                }
                n++;
            }
        }

但是，我觉得有一种方法可以更有效地编写此代码，因为我的目标是用更高的数字（例如 200,000 左右）达到相同的时间。这是我的秒表代码，如果需要，我会在单击按钮时执行该代码：

    var timer = new Stopwatch();
            timer.Start();
            ListThePrimes();
            timer.Stop();
            TimeSpan timeTaken = timer.Elapsed;
            string foo = timeTaken.ToString(@"m\:ss\.fff");
            MessageBox.Show("The sum is " + sum + ". It took this program " + foo + " seconds to run.");

如果有人能告诉我是否有更有效的方法来执行此操作，我将不胜感激。

Answer 1

您需要优化获取素数的方式，您的方式效率极低。这样做的常用方法是使用 Sieve of Eratosthenes。使用这种方法，我可以轻松地在几毫秒内得到 100000 以内的所有素数。除此之外，对它们求和是微不足道的。

var n = 100000;
var a = Enumerable.Range(0,n+1).Select(_ => true).ToArray();

for(var i=2;i<Math.Sqrt(n);i++)
{
    if(a[i])
    {
        for(var j = i*i;j<=n;j += i)
        {
            a[j] = false;
        }
    }
}

var result = a.Select( (x,i) => new {IsPrime = x,Prime = i})  
              .Where(x => x.IsPrime && x.Prime > 1) 
              .Sum(x => x.Prime);
    
Console.WriteLine(result);

实例：https://dotnetfiddle.net/eBelZD

Answer 2

你真的要好好研究你的质数法了。一种新方法是 Erathostenes 筛，但您当前的代码也可以改进很多。

去掉output等不需要的变量，直接放在if标签中即可。
你可以将你检查的数字减半，因为质数只能是奇数，所以不要做 n++ 但 n+=2;.

什么是找到素数总和的更有效方法？

What's a more efficient way to find sum of prime numbers?

c#

algorithm

primes