The Sieve of Eratosthenes in C#

In some of the Project Euler problems we have needed a source of primes. One algorithm for finding primes is called the Sieve of Eratosthenes. This algorithm is both pretty simple to understand and to implement. It is also fairly fast and usable, at least for the lower primes.

My implementation is based upon the algorithm described on the Wikipedia page and some helpful optimizations I found in an article at Black Wasp. The differences from the original algorithm and the solution at Black Wasp is that it finds the primes incrementally and that it only looks for a new prime when asked.

My code should be pretty self explanatory, but the basic idea is that we have a list of known primes and for each odd number we check it against the these. If a number is not evenly divisible by any of the known primes, then we have found a new one and can add it to our list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Eratosthenes : IEnumerable<ulong>
{
    private readonly List<ulong> knownPrimes;

    public Eratosthenes()
    {
        knownPrimes = new List<ulong> {2, 3};
    }

    public IEnumerator<ulong> GetEnumerator()
    {
        // Return the ones we know first
        foreach (var prime in knownPrimes)
            yield return prime;

        // Then find new ones
        var possible = knownPrimes.Last();
        while (true)
            if (IsPrime(possible += 2))
            {
                yield return possible;
                knownPrimes.Add(possible);
            }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
     
    private bool IsPrime(ulong value)
    {
        var sqrt = (ulong) Math.Sqrt(value);
        return ! knownPrimes
            .TakeWhile(x => x <= sqrt)
            .Any(x => value%x == 0);
    }
}

How do you use it? Simple! For example, to print the first 500 primes you can do this:

var primes = new Eratosthenes().Take(500);

foreach(var prime in primes)
{
    Console.WriteLine(prime);
}

And that’s all there is to it! What do you think? Let me know if you have any questions about it or any suggestions to how it can be improved. I want to know ;)

  • http://www.gleocadie.net Gregory LEOCADIE

    I like your code.

    I don’t want to be picky, but line 17, replace primes by knownPrimes.

    You can avoid using sqrt (line 33), instead, you can rewrite line 35 as

    .takeWhile (x => x * x > value)

    Again, there are faster ways, but your code remains clear, and elegant. ;)
    cheers
    Gregory

    • http://www.geekality.net Torleif

      Pickyness is more than welcome. Seems like an unnoticed bug has snuck itself in there on line 17, yes. Fixed it now! Thanks for noticing and letting me know ;)

      Is one sqrt worse than many multiplications? Will have to test that some time. Unfortunately my developer machine is dead at the moment, but I will try to remember to check it out some time, hehe. Or maybe if you have the curiosity and time you could test it out yourself and do some benchmarks. Please let me know if you do!

  • http://www.gleocadie.net Gregory LEOCADIE

    Oh good point. It was just another way, and not so good after all.
    I’ll make some benchmarks ;)

  • http://www.gleocadie.net Gregory LEOCADIE

    It seems that my version is a little bit faster (I’ll do more tests). I think that the comparison in the TakeWhile (double against ulong) is the culprit (the compiler has to generate more code to handle it).

    • http://www.geekality.net Torleif

      In yours or mine? Cause I cast the result of the sqrt to a ulong, so there shouldn’t be any comparisons between double and ulong. Unless I’m missing something here…

      • http://www.gleocadie.net Gregory LEOCADIE

        mine…
        Damn it…I should be more careful…
        Ok, I learned 2 things:
        – if a modification occurs in a copy/past code, check the my mouth before speaking
        – LINQ is good :D

        • http://www.geekality.net Torleif

          :D

  • Daniel

    I must point out this isn’t actually the Sieve of Eratostenes but trial division by primes. By definition, a sieve takes a finite set of numbers and eliminates elements of the set. In contrast, you are grabbing the next odd number and checking its primality via trial division. If you would like to increase the efficiency of your algorithm, may I suggest you use a more efficient primality test: http://en.wikipedia.org/wiki/Prime_number#Primality_testing_vs._primality_proving

    • http://www.geekality.net Torleif

      Oh really? Interesting. Maybe I might have to create a new post then with the real one, hehe. I thought this was pretty much the same, but I see your point! Thanks for the out-pointing :)

      Do you have a good primality you can suggest? Have looked into that a bit, but found the whole thing a bit confusing. Seemed most of those tests didn’t really prove it’s a prime, but rather tell you it might be? And for generating a series of primes that seemed a bit risky…