Primes

The Problem

Your non-technical manager assigns you the task to find all primes between 1 and 10^8. The assumption is that your company is going to use a parallel machine that supports eight concurrent threads. Thus, in your design you should plan to spawn 8 threads that will perform the necessary computation. Your boss does not have a strong technical background but she is a reasonable person. Therefore, she expects to see that the work is distributed such that the computational execution time is approximately equivalent among the threads.

Required Output

Please print the following output to a file named primes.txt:

<execution time>  <total number of primes found>  <sum of all primes found>
<top ten maximum primes, listed in order from lowest to highest>

Running the Code

Assuming you're running on a Unix-like system, you'll need to have make installed as well as C++17:

In the root directory, run make run to run the code. This compiles everything into a directory named out then runs that executable. The results will be written to a file under the out directory called primes.txt.
You can also run make clean to remove files in the out directory generated by make.

If you're on Windows and don't have make installed, you can run the following (make sure you're in the root directory):

mkdir out
g++ -std=c++17 src\primes.cpp -o .\out\primes -Wall -lpthread
.\out\primes.exe

An Analysis of the Algorithm

This assignment uses the Sieve of Eratosthenes algorithm to find all prime numbers from 2 to 100,000,000 (excluding 0 and 1 since they're not prime). This normally works by creating a list of consecutive integers from p, which is 2 in this case, and eliminating all multiples of p counting in increments of p from 2p to n, so 3p, 4p, 5p, 6p, ...; (note that p itself will not be marked).

In order to apply this to a multi-threaded environment, we can create some number of threads T and increment our p value as (2 + T)p, (3 + T)p, ... In the above explanation, we counted in increments of p, in this multi-threaded environment, we'll count in increments of T. For example, say we have 4 threads:

Thread #1 marks multiples starting at 2, then all multiples starting at 6, then 10, and so on.
Thread #2 marks multiples starting at 3, then all multiples starting at 7, then 11, and so on.
Thread #3 marks multiples starting at 4, then all multiples starting at 8, then 12, and so on.
Thread #4 marks multiples starting at 5, then all multiples starting at 9, then 13, and so on.

By doing so, we can split up the workload fairly evenly between any number of threads. The Sieve of Eratosthenes has a runtime of O(n log log n) so we could say that the multi-threaded approach is O((n log log n) / T), where T is the number of threads used.

An Analysis of the Code

In order to find all primes, we first need to create an array capable of keeping track of what numbers are prime. To do so, a boolean array of size N + 1 (where N is the number of primes) is created with all values initially initialized to true. The Sieve algorithm (as described above), will mark all numbers that aren't prime as false. After it's finished, any values that are marked as true in the array are prime.

The following shows the time it takes to find all prime numbers up to 100,000,000 based on the number of threads (each trial was run 5 times with the lowest value taken from each):

Thread count	Execution time
1	862.42ms
2	853.09ms
3	572.26ms
4	492.45ms
5	452.30ms
6	448.53ms
7	426.19ms
8	381.21ms