As the name of the algorithm stems from the Greek mathematician Eratosthenes of Cyrene, it is called "Sieve of Eratosthenes".

Let

*N*be the upper bound, then the algorithm can be described as follows:

All numbers from 2 to

*N*are written down. The smallest not crossed out number at all times is a prime number. At start this is the 2.

From then on, all multiples of this number are crossed out, it suffices to start with the square of the number.

Now here the code of a C# - console application doing exactly that:

class SiebDesEratosthenes

{

static void Main(string[] args)

{

Console.WriteLine("Geben Sie die obere Grenze ein:");

int UpperBound = int.Parse(Console.ReadLine()); // input upper bound

bool[] Tagged = new bool[UpperBound + 1]; // array describing which numbers are crossed out

// initialise arrays

for (int i = 0; i < Tagged.Length; i++)

Tagged[i] = false;

// iterate over all numbers up to the square root of the upper bound

for (int i = 2; i < Math.Ceiling(Math.Sqrt(UpperBound)); i++)

{

if (!Tagged[i])

{

int j = i;

// cross out all multiples

while (j * i <= UpperBound)

{

Tagged[j * i] = true;

j++;

}

}

}

// alle nicht durchgestrichenen Zahlen ausgeben

for (int i = 2; i < Tagged.Length; i++)

{

if (!Tagged[i])

Console.Write(i.ToString() + " ");

}

}

}

## No comments:

## Post a Comment