Sieve of Eratosthenes in C# with LINQ

Question

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 < sqrt(n)
   set M = next number in LIST > 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 <= 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 4

• Runs total = 100000; in 0.008 secs
• Runs total = 1000000; in 0.141 secs
• Runs total = 10000000; in 2.973 secs

Answer 1

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.

Answer 2

You're accessing modified closures in your LINQ statements, so I'd copy them to locals.

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

        while (cur <= Math.Sqrt(Total))
        {
            var cur1 = cur;
            var cur2 = pc.First(i => i > cur1);

            pc.RemoveAll(i => i != cur2 && i % cur2 == 0);
            cur = cur2;
        }

        Console.WriteLine(pc.Max());

Answer 3

update: as tested and explained by @Guffa and @EoinCampbell, this is actually much slower.

The benefits of a HashSet are mainly in access speed by index.
Since the algorithm never even accesses the list by index, the Hashset will merely introduce additional overhead with the hashing and storing of the internal structure for fast access.

---

I would user HashSet<int> instead of List<int>.

The only change needed would be in the while, .RemoveWhere() instead of .RemoveAll(): http://msdn.microsoft.com/en-us/library/bb361254.aspx

Answer 4

I found an answer on Stack Overflow a few days ago. I adapted it a bit to make it more parallel and easier to read.

I might have made a mistake. I tested it in my computer: Core i7 Second Gen (3GHz) with 12GB of RAM.

It took a few seconds to solve most of the numbers less than 50,000,000. However, it took around 6:32 seconds to solve 100,000,000. It took around 47 mins to solve 500,000,000. It crashed 11 hours after solving 1.5 billion.

private static void GetPrimeNumbers(int max)
{
    var allPossibleNumbers = Enumerable.Range(3, max-3);
    var possiblePrime = allPossibleNumbers
            .AsParallel()
            .Where(n => Enumerable.Range(2, (int)Math.Sqrt(n))
                                  .All(i => n % i != 0)
            )
            ;
    possiblePrime
            .ToArray()
            .AsParallel()
            .Dump()
            ;
}