Jan 24 2010
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);
}
}
Read the rest of “Sieve (of Eratosthenes) algorithm for generating prime numbers” …












Masakatsu, “True Victory”.
“The most important thing for a human being is not what is between his or her ears; it is what is in his or her heart. If the spirit is strong, one can accomplish anything.




I am (re)reading a book on Aikido called “KI In Daily Life” by Koichi Tohei. Aikido has a very deep personal meaning to me and it has definitely shaped the way I go through life and interact with others.










