you will be exploring a method of counting the prime numbers between 1 and N. You will use 8 threads, and each will be given a range in which to count primes. Sequential Download the sequential solution, prime_search_seq.c, read it, compile it, run it, and embrace it. You need to understand the algorithm that decides whether a number is a prime or not. Parallel Each thread counts a section of the set of numbers, i.e. numbers between 1 and N. The first thread gets numbers 1 through N/8, the second thread gets numbers N/8+1 through 2*N/8, etc. It is alright to mandate that N be a multiple of 8 so that it divides evenly among the threads. It does not matter if N is a global variable, constant, or command line input. The sequential code defines N=800000 which is a large enough number. To test the Pthreads version, just time it and compare it to the sequential version. Use a local variable to keep track of an individual thread's prime number count. Then, before the thread exits, place the value in a variable the main code can access in order to calculate the final sum. I do this after each thread is joined.

----------------------------------------------------------------------------------------------------------------

/* prime_search_seq.c * Stephanie Taylor * Count the number of prime numbers up to and including FINAL_NUM * This is the sequential version. */

#include #include #include #include #include

//Global constants #define NUMTHREADS 8 #define FINAL_NUM (100000*8)

//Type definitions typedef struct { int id; } parm;

// Global variables int global_count = 0;

// Return 1 if n is prime, else 0 int is_prime(int n) { if (n < 2) return 0; if (n == 2) return 1; if (n % 2 == 0) return 0; int i; for (i=3; i < n; i += 2) { if (n % i == 0) return 0; } return 1; }

/* Main routine. */ int main(int argc, char* argv[]) { int i; int count = 0;

for (i=1; i<=FINAL_NUM; i++) { if (is_prime(i)) { //printf("%d: %d is prime ",id,i); count++; } }

int denom = FINAL_NUM; printf("There are %d prime numbers <= %d ",count,FINAL_NUM); // printf("That is a ratio of %f, which should be about %f ", (double)count/(double)denom, 1.0/log((double)denom)); printf("That is a ratio of %f ", (double)count/(double)denom);

return 0; } // end main