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  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  i > cur);
    pc.RemoveAll(i => i != cur && 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 <= Math.Sqrt(notPrime.Length); i++) {
  if (!notPrime[i]) {
    for (int j = i * 2; j < 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.

StackExchange Code Review Q#6115, answer score: 10