Enumerable.Range (...). Any (...) transcends the base cycle: Why?

Question

I adapted a simple one-line prime generator from Scala to C # (mentioned in a comment on

Answer 1

For each iteration of the for loop, you find the square root of n. Make a cache instead.

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

And as already mentioned, break the for loop as soon as you find the factor.

Answer 2

Enumerable.Any originates if the condition is successful while your loop is not running.

The source enumeration stops as soon as the result can be determined.

This is an example of a bad test. Try changing your loop and see the difference:

  if (n % i == 0) { hasFactor = true; break; } } throw new InvalidOperationException("Cannot satisfy criteria."); 

Answer 3

In LINQ version short circuits, your loop is not. By this, I mean that when you determine that a particular integer is actually a factor, the LINQ code stops, returns it, and then jumps. Your code continues the loop until it completes.

If you change the for to include this short circuit, you should see a 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;; } } } 

Answer 4

It seems like a criminal:

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

You should exit the loop as soon as you find the factor:

 if (n % i == 0){ hasFactor = true; break; } 

And, as others have pointed out, move the Math.Sqrt call outside the loop so you don't call it every loop.

Answer 5

In the name of optimization, you can be a little smarter about this by avoiding even numbers after 2:

 if (n % 2 != 0) { int quux = (int)Math.Sqrt(n); for (int i = 3; i <= quux; i += 2) { if (n % i == 0) return n; } } 

There are several other ways to optimize simple searches, but this is one of the easiest ways and a big win.

Edit: you might consider using (int) Math.Sqrt (n) + 1. FP + rounding down functions could potentially skip the square of a large prime.

Answer 6

At least part of the problem is the number of times Math.Sqrt . This is done once in the LINQ query, but in the loop example, it is executed N times. Try pulling it to local and repurposing the application. This will give you a more characteristic breakthrough.

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