Enumerable.Range(...).Any(...) outperforms a basic loop: Why?

Question

I was adapting a simple prime-number generation one-liner from Scala to C# (mentioned in a comment on this blog by its author). I came up with the following:

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

It works, returning the same results I'd get from running the code referenced in the blog. In fact, it works fairly quickly. In LinqPad, it generated the 100,000th prime in about 1 second. Out of curiosity, I rewrote it without Enumerable.Range() and 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;
  }
}

Intuitively, I'd expect them to either run at the same speed, or even for the latter to run a little faster. In actuality, computing the same value (100,000th prime) with the second method, takes 12 seconds - It's a staggering difference.

So what's going on here? There must be fundamentally something extra happening in the second approach that's eating up CPU cycles, or some optimization going on the background of the Linq examples. Anybody know why?

Answer 1

For every iteration of the for loop, you are finding the square root of n. Cache it instead.

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

And as other have mentioned, break the for loop as soon as you find a factor.

Answer 2

The LINQ version short circuits, your loop does not. By this I mean that when you have determined that a particular integer is in fact a factor the LINQ code stops, returns it, and then moves on. Your code keeps looping until it's done.

If you change the for to include that short circuit, you should see similar performance:

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