Parallel Implementation and Performance Analysis of the Sieve of Eratosthenes

Design parallel algorithms and implement the parallel algorithm efficiently using C and OpenMP. Measure the performance and analyze the results. Parallel algorithm design in detail How to distribute the n-1 numbers to t threads for any n and t, where t is the number of threads? What is the total number of numbers assigned to each process? How find the next prime number used for sieve? How to calculate the total number of primes? How to handle communications? Parallel implementation and programming How to implement the parallel algorithms for a shared memory system using OpenMP? How to implement it more efficiently? Add a project description in the code. Add comments to all variables and all important code segments. Results and comparison When executing your parallel program, the user will specify t and enter n for input. Include screenshots showing how to compile and execute the parallel program. The results should include (1)the total number of prime numbers if n = 1,000,000 and (2) print out the first 100 prime numbers. Compare the parallel results with the results in Phases 1 and 2. Performance results and analysis You will need to collect serial runtime (t =1) and parallel runtimes with respect to different n and t. Calculate the speedup and efficiency. List the results of parallel runtime, speedup and efficiency in three tables. Discuss how the parallel runtime, speedup and efficiency change with respect to different p or t. OpenMP and C source code are needed.