找到质数总和的更有效方法是什么？ 我正在研究一个程序，该程序跟踪将所有质数的总和达到一定数字所需的时间，并试图找到获得此val的最有效方法...

Question

，但是，我觉得有一种方法可以更有效地编写此代码，因为我的目标是达到相同的时间，数量更高，例如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

的sive。使用此方法，我可以轻松地获得最高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);

live示例：

Answer 1

您确实必须处理您的质子数方法。一种新的方法将是Erathostenes筛子，但是您当前的代码也可以得到很多改进。

themove不必要的变量，例如输出，只需将其直接放在if tag中。

您可以检查的数字一半，因为素数只能是奇数数字，所以不要做n ++，而是n+= 2;。

与使用某种数字理论和组合学相比，您可以使您的效率更高。通常，如果您具有f（n）的函数f（n），并且您想总和∑_p f（p），那么您可以使用

möbius函数

Answer 2

的原则coverert ∑_p f（p）= ∑_n µ（n）.f（n/n，n），其中f（n/n，n）= ∑_ { M = 1至N/N} F（N.M）。基本上F（n/n，n）是n≤n的所有倍数的总和。

基本上，我们正在求和所有数字f（n，1），然后减去所有是prime p，f（n/p，p）的倍数的所有数字，但是我们将所有是p.q倍数的数字减去所有数字对于两个素数。因此，我们需要添加F（N/（P.Q），P.Q）。但是随后我们仔细计数数字是P.Q.R等的倍数

非平方数字的möbius函数为零，否则具有正确的符号。 thus，∑_p f（p）= ∑_n [µ（n）.n]。（n/n）。（n/n+1）/2（隐含整数除法）。然后，我们可以使用dirichlet双曲线方法

降低sublinear的复杂性。
1. 这是数字理论编程问题所需的非常典型的策略。