Sieve of Eratosthenes in C# with LINQ Can someone look over this Sieve of Eratosthenes implementation? It seems almost too easy.

Rather than maintaining a seperate bit[] to track prime/not prime, I'm just removing the noncandidates from the collection completely on each iteration.

Pseudocode

LIST = 2...n

set M = 1
while M &lt; sqrt(n)
   set M = next number in LIST &gt; M
   remove all multiples of M (excluding M itself) from LIST


C#

int cur = 1, total = 1000;
var pc = Enumerable.Range(2, total).ToList();

while(cur &lt;= Math.Sqrt(total))
{
    cur = pc.First(i =&gt; i &gt; cur);
    pc.RemoveAll(i =&gt; i != cur &amp;&amp; i % cur == 0);
}

Console.WriteLine(pc.Max());


It just seems a bit too easy. Results seem right though. In LINQPad 4


Runs total = 100000; in 0.008 secs
Runs total = 1000000; in 0.141 secs
Runs total = 10000000; in 2.973 secs
Yes, it works, but it's slow.

I compared it to this:

bool[] notPrime = new bool[total];
notPrime[0] = true;
notPrime[1] = true;
for (int i = 2; i &lt;= Math.Sqrt(notPrime.Length); i++) {
  if (!notPrime[i]) {
    for (int j = i * 2; j &lt; notPrime.Length; j += i) {
      notPrime[j] = true;
    }
  }
}


(I used Enumerable.Range(2, total - 2) in the Linq code to make it produce the numbers 2 to 99999 rather than 2 to 100001.)

For total = 100000, average for 100 executions:

Linq 27.696966 ms., 0.280000 collections
Array 0.708616 ms., 0.030000 collections


So, it takes a lot of time, and does more garbage collections.