// From the ECMA-334 C# Language specifications (section 17.8).
// Also in Hejlsberg et al., The C# Programming Language, 2ed.
using System;
class CountPrimes
{
static int Count(int max) {
BitArray flags = new BitArray(max + 1);
int count = 1;
for (int i = 2; i <= max; i++) {
if (!flags[i]) {
for (int j = i * 2; j <= max; j += i) flags[j] = true;
count++;
}
}
return count;
}
static void Main(string[] args) {
int max = int.Parse(args[0]);
int count = Count(max);
Console.WriteLine("Found {0} primes between 1 and {1}", count, max);
}
} | |
Counts the number of primes less than max.
Makes a bit array with all
elements initialized to false.
Set flags[i*2], flags[i*3], ... to true.
Counts i as a prime.
The main program which calls
the Count method from above.
|