Due Date: Sep. 8, 2014

For this assignment, you will use Posix Pthreads to implement a parallel version of the Sieve of Erasthosenes prime finding algorithm. You will run your program on the departmental machines

- Create a list of natural numbers - 1, 2, 3, ...
*max*. - Set
*k*to 2, the first unmarked number in the list. - Repeat:
- Mark all multiples of
*k*between*k*^2 and*max*. - Find the smallest number greater than
*k*that is still unmarked. - Set
*k*to this new value. - Do steps 1- 3 until
*k*^2 is greater than*max*.

- Mark all multiples of
- The unmarked numbers are prime.

- First sequentially compute primes up to sqrt(
*max*). - Given
*p*cores, build*p*chunks of roughly equal length covering the range from sqrt(*max*) + 1 to*max*, and allocate a thread for each chunk. - Each thread uses the sequentially computed "seeds" to mark the numbers in its chunk.
- The master waits for all threads to finish and collects the unmarked numbers.