Sieve (of Eratosthenes) algorithm for generating prime numbers

A prime number is divisible by 1 or by itself. To generate prime numbers to 20 we’ll use Sieve (of Eratosthenes) algorithm, which is really simple to explain:

Strike out all multiples of 2′s:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Strike out all multiples of 3′s:

2 3 5 7 9 11 13 15 17 19

And so on. Here is a C# code that does exactly that:

      
private static void PrintPrimesTo(int num) {
            var primes = new bool[num + 1];

            // init candidates
            for (int i = 2; i <= num; i++) { primes[i] = true; }

            // cross-out 2's:
            //   2, 4, 6, 8, 10...
            // cross-out 3's:
            //   9, 12, 15...
            for (int i = 2; (i * i) <= num; i++ ) {
                Console.WriteLine("Crossing out {0}'s to {1}:", i, num);

                for (int j = i * i; j <= num; j = j + i) {
                    Console.WriteLine(" * crossing-out: {0}", j);
                    primes[j] = false;
                }
            }

            Console.WriteLine("Results: prime numbers between 2 and {0}:", num);
            for (int i = 2; i <= num; i++) {
                if (primes[i]) Console.WriteLine(" * {0} ", i);
            }
        }


Sample output from calling PrintPrimesTo(100):

Crossing out 2's to 20:
 * crossing-out: 4
 * crossing-out: 6
 * crossing-out: 8
 * crossing-out: 10
 * crossing-out: 12
 * crossing-out: 14
 * crossing-out: 16
 * crossing-out: 18
 * crossing-out: 20
Crossing out 3's to 20:
 * crossing-out: 9
 * crossing-out: 12
 * crossing-out: 15
 * crossing-out: 18
Crossing out 4's to 20:
 * crossing-out: 16
 * crossing-out: 20
Results: prime numbers between 2 and 20:
 * 2
 * 3
 * 5
 * 7
 * 11
 * 13
 * 17
 * 19

8 thoughts on “Sieve (of Eratosthenes) algorithm for generating prime numbers

  1. Cam

    This is great – you can also create a single loop which ‘crosses out’ multiples of other primes up to quite a bit… by unrolling the loop and finding the pattern of multiples, which always repeats. Having a hard-coded loop which eliminates multiples turns out to be very performant as well… This is one aspect of my favorite interview question, how to determine if a number is prime? Lots of fun.

    I once had a team challenge where everyone on the team implemented their own algorithm to see who could make the fastest prime detector.

    The best part about this is that there are so many layers of the answer, it’s easy to talk about the problem at many levels and depths of optimization…

  2. Dan Madden

    It’s funny I was just reading about this method this morning in the book “Mathematics from the birth of numbers”

Leave a Reply