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.PseudocodeLIST = 2...nset M = 1while M < sqrt(n)   set M = next number in LIST > M   remove all multiples of M (excluding M itself) from LISTC#int cur = 1, total = 1000;var pc = Enumerable.Range(2, total).ToList();while(cur <= Math.Sqrt(total)){    cur = pc.First(i => 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 4Runs total = 100000; in 0.008 secsRuns total = 1000000; in 0.141 secsRuns total = 10000000; in 2.973 secs
Sieve of Eratosthenes in C# with LINQ
c#;linq;sieve of eratosthenes
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 collectionsArray 0.708616 ms., 0.030000 collectionsSo, it takes a lot of time, and does more garbage collections.