Description
Your task for this assignment is to implement a prime number finding program that utilizes multiple threads via OpenMP.
Prime numbers are useful in a variety of applications but probably most importantly in cryptography.
For example, you may wish to look over the Wikipedia page for RSA. Your program should return the number of unique primes that it was able to find within consecutive powers of ten. As far as the method used for determining primes, there are many possible approaches.
One simple approach is to try dividing your candidate n by values 2,3,…√n. If the remainder is zero, then your n value is not prime. There are likely faster algorithms for producing prime values. This may take a potentially long amount of time. The sizeable amounts of computation make this problem a good candidate for parallelizing via OpenMP.
Fortunately, there is very little coordination required among the different threads. Your program should find all primes under 100,000,000. The starter code will find the primes in a serial fashion but may not parallelize well. You may need to consider re-writing some of the logic to make the code more amenable for OpenMP. Also, you may need to mark some sections as critical.
Hopefully everyone can run their program on multiple cores. Hopefully Submitty will allow us to use multiple cores as well 🙂 bash$ ./a.out 10 4 100 25 1000 168 10000 1229 100000 9592 1000000 78498 10000000 664579 100000000 5761455
