Enumerable.Range(...).任何(...)都优于基本循环:为什么？

Question

我正在调整从Scala到C#的简单素数生成单行(在其博客作者的评论中提到).我想出了以下内容:

int NextPrime(int from)
{
  while(true)
  {
    n++;
    if (!Enumerable.Range(2, (int)Math.Sqrt(n) - 1).Any((i) => n % i == 0))
      return n;
  }
} 

它可以工作,返回我从运行博客中引用的代码得到的相同结果.事实上,它运作得相当快.在LinqPad中,它在大约1秒内产生了第100,000个素数.出于好奇,我重写它不Enumerable.Range()和Any():

int NextPrimeB(int from)
{
  while(true)
  {
    n++;
    bool hasFactor = false;
    for (int i = 2; i <= (int)Math.Sqrt(n); i++)
    {
        if (n % i == 0) hasFactor = true;
    }
    if (!hasFactor) return n;
  }
}

直观地说,我希望它们能够以相同的速度运行,或者甚至让后者以更快的速度运行.实际上,使用第二种方法计算相同的值(第100,000个素数)需要12秒 - 这是一个惊人的差异.

那么这里发生了什么？从根本上说,在第二种方法中会出现额外的事情,这会占用CPU周期,或者在Linq示例的背景下进行一些优化.谁知道为什么？

Answer 1

对于for循环的每次迭代,您都会找到n的平方根.请改为缓存它.

int root = (int)Math.Sqrt(n);
for (int i = 2; i <= root; i++)

正如其他人提到的那样,一旦找到一个因素就打破for循环.