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

Advertisements