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);
}
}

Continue reading →