##
Sieve of Eratosthenes Kata

Posted by Daniel Elliott under

c#,

Coding,

Kata
1 Comment
I have finally got down to doing the first of my programming Kata. (Or am just about to start to anyway!) After some head scratching and a more than healthy dose of procrastination, I decided upon the Sieve of Eratosthenes as my first exercise. It is a simple way to discern prime numbers up to a limit n.

The wikipedia algorithm for the problem is below:

1. Write a list of numbers from 2 to the largest number you want to test for primality. Call this List A. (This is the list of squares on the left-hand-side of the picture.)

2. Write the number 2, the first prime number, in another list for primes found. Call this List B. (This is the list on the right-hand-side of the picture.)

3. Strike off 2 and all multiples of 2 from List A.

4. The first remaining number in the list is a prime number. Write this number into List B.

5. Strike off this number and all multiples of this number from List A. The crossing-off of multiples can be started at the square of the number, as lower multiples have already been crossed out in previous steps.

6. Repeat steps 4 through 6 until no more numbers are left in List A.

In actuality, with preparation for my interview process for my new job (YAAY!) this did not get done until a couple of days later. Here is my first practice; I will post my other katas as I devise them and then try to show how the practice evolves through time.

using System;

using System.Collections.Generic;

namespace sieve050707

{

class MainClass

{

public static void Main(string[] args)

{

Console.WriteLine(“Sieve of Eratosthenes – 05 July 2007″);

int sampleSize = 100;

if (args.Length > 0)

{

sampleSize = Int32.Parse(args[0]);

}

List sampleData = new List();

List primesFound = new List();

for (int counter=2; counter < sampleSize; counter++)

{

sampleData.Add(counter);

}

for (int counter=2; counter < sampleSize; counter++)

{

if(sampleData.Contains(counter))

{

primesFound.Add(counter);

sampleData.Remove(counter);

for (int multiple=counter*2; multiple < sampleSize; multiple = multiple + counter)

{

sampleData.Remove(multiple);

}

}

}

foreach(int prime in primesFound)

{

Console.WriteLine(prime.ToString() + ” is prime”);

}

}

}

}

### Like this:

Like Loading...

*Related*

July 10, 2007 at 5:05 pm

[…] After a topsy-turvy time, I finally got the first of my Kata done. I used the Sieve of Eratosthenes algorithm as my first […]