OpenMP Prime Finder
Your task for this assignment is to implement a prime number finding program that utilizes multiple threads
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 🙂