## duminică, 9 ianuarie 2011

### C# implementation of the parallel sieve of Erathostenes

This is my implementation of a parallel sieve of Erathostenes in C#.
I got the algorithm from here.
I know I could have used some of the existing C# functionality to manage threads rather than doing it all myself but I found this more convenient at the time.
Anyone is welcomed to bring any corrections.

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ParalelErathostenes
{
///
/// Finds prime numbers starting from 2 and up to a given value
///
class Program
{

/*
1. Create a list of natural numbers 2, 3, 4, 5, ….., n.  None of which is marked. Each process
creates its share of lists.
2. Set k to 2, the first unmarked number on the list. Each process does this.
3. Repeat: Each process marks its share of list
a. Mark all multiples of k between k² and n.
b. Find the smallest number greater than k that is unmarked. Set  k to this new
value
c. Process 0 broadcasts k to rest of processes.
Until k² > n.
4. The unmarked numbers are primes.
5. Reduction to determine number of primes
*/

///
/// possible status of each thread used by this program
///
{
DoingStuff = 0,
Waiting = 1,
};

///
/// Statuses for all the threads started
///

///
/// array that stores wether a number is prime or not true = prime, false = not prime
/// this array should be as long as the maximum number up to which you want to find primes
///
static bool[] nums;

///
/// k from the algorithm above
///
static int k;

///
/// n from the algorithm above
///
static int n;

///
/// nr of threads that compute primes - this is actually the number of worker threads because one
/// extra thread will handle just finding the smallest remainig prime and broadcasting it to all the
///

///
/// changes status of all worker threads to "DoingStuff"
///
{
for (int i = 1; i < nrThreads + 1; i++)
{
}
}

///
/// changes status of all worker threads to "Waiting"
///
{
for (int i = 1; i < nrThreads + 1; i++)
{
}
}

///
///
{
for (int i = 1; i < nrThreads + 1; i++)
{
}
}

///
/// checks wether at least one of the worker threads is still doning something
///
///
{
for (int i = 1; i < nrThreads + 1; i++)
{
return true;
}
return false;
}

///
/// checks wether at least one of the worker threads is waiting(on stand by)
///
///
{
for (int i = 1; i < nrThreads + 1; i++)
{
return true;
}
return false;
}

///
/// checks wether the main thread is in wairing mode
///
///
{
}

///
/// checks if all threads are done working and waiting
///
///
{
{
return false;
}

return true;
}

///
/// each thread runs this function it marks non prime numbers within it's given range
/// between start and stop
///
///

{

{
}

return;
//stores how many numbers we have to decide are primes or non primes
int nrOfNumbers = n - k * k;
//divide that by the number of threads to get the interval within which each thread should
//look for primes
int interval = nrOfNumbers / nrThreads;

//for this thread and this value of k start at this value
int startNumber = k * k + interval * (ThreadNr - 1);
//and end at this value
int stopNumber = (ThreadNr == nrThreads) ? n : startNumber + interval;

lock (nums)
{
for (int j = startNumber; j < stopNumber; j++)
{
//Mark all multiples of k between k² and n.
if (j % k == 0)
nums[j] = false;
}
}

//nothig to do now but wait

}

///
/// this is the main thread's function it manages the worker therads and finds the smallest prime
/// when the worker threads finish marking non primes
///
{
{
}

//c. Process 0 broadcasts k to rest of processes.
for (int i = k + 1; i < n; i++)
{
if (nums[i])
{

k = i;

break;
}
}
//Until k² > n.
if (k * k > n)
{
//commit suicide
return;
}
//all worker threads can now read the correct new value of k so they can all get to work

}

static void Main(string[] args)
{

n = 100;

//add one because one main thread is needed to manage all the others

//1. Create a list of natural numbers 2, 3, 4, 5, ….., n.  None of which is marked.
nums = new bool[n];
//suppose all these are primes, we will then start marking them as non primes
for (int i = 2; i < n; i++)
nums[i] = true;

//initialize k with 1, start looking for primes bigger than 1, 1 is not a prime
k = 1;

//make sure all threads are waiting so they don't run out and find primes on their
//own without the main thread regulating them

for (int i = 1; i < nrThreads + 1; i++)
{
//need to declare this as a locol variable so that the value passed to the thread
//won't be changed causing chaos
var localI = i;

}

//wait for all threads to end
//commenting the line above and decommenting the one below really help with debugging
//while (true)
{
}

//print the primes you found
for (int i = 0; i < n; i++)
if (nums[i])
Console.WriteLine(i);
}
}
}
```