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 |
1
