求素数和的更有效方法是什么？

疯狂的程序员

我正在开发一个程序，该程序跟踪将所有质数的总和达到某个数字所需的时间，并试图找到获得该值的最有效方法，因为我有一个秒表 (System.诊断）跟踪需要多长时间。目前，我可以使用以下代码在大约 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.");

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

杰米克

您需要优化获得素数的方式，您的方式效率极低。这样做的常用方法是使用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

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。