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
