Dmitry Kalashnikov

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