Multi-thread C++ program to find all prime numbers < N

In this article, we have developed a Multi-thread C++ program to find all prime numbers < N. We have covered Sieve or Eratosthenes algorithm and used thread in C++.

Introduction

There are many ways to generate prime numbers.

In this article we will focus on the Sieve or Eratosthenes, which has been implemented in this article too.

The downsize of this approach is that for each number, the algorithm waits to finish the marked numbers of the predecessor prime number;

Could we do that in parallel ?

A way of implementation

My approach is to use a matrix with N lines and 2 columns stored in a class named Prime. Each line will represent a number stored in the first column and the status of it stored in the second columnd that could be:

0 if the number is composite
1 if the number is prime

The constructor will alocate memory and initialize the matrix with all numbers marked with 1 assumed that all are primes.

        Prime(int N)
            {
                this->N = N;

                primes = new int *[N];

                for(int i=0; i < N; i++)
                    primes[i] = new int[2],
                    primes[i][0] = i,
                    primes[i][1] = 1; // mark all as prime numbers
            }

For each number starting with 2 until sqrt(N) we can call the eliminate function that will mark the composite numbers with 0 in increments of the p, except for the parameter p that will not be changed.

        void eliminate(int p)
        {
            int i = p + p;
            while (i < N)
                primes[i][1] = 0, // mark the multiplicies of p as not primes 
                i+=p;
        }

We can call this function in a serie or a parallel way.

The first one can be done by simply call of the function in a for loop

    for(int i= 2; i < sqrt(N) ; i++)
        p.eliminate(i);

The second one uses a vector of threads that can be run in parallel

    for(int i= 2; i < sqrt(N) ; i++)
        v.push_back( thread (&Prime::eliminate, ref(p), i ) );

A thread is basically a piece of statements that can be executed in parallel by sharing the same resources.
Storing the threads in a vector will make us life easier, because we can join them easier later on:

    for (auto& th : v) th.join();  

Joining a thread it means it blocks the execution of the thread that calls this function until the function called in construction returns.

The echivalent statement from above could be written in another way

   for(int i= 0; i < sqrt(N) -2; i++)
        v[i].join();

or

    for(int i= 0; i < sqrt(N) -2; i++)
        v.at(i).join();

Notice the start of i from 0 ! because we push threads into it starting with the first element even though i was equal with 2 when we did that.

The output is written in a text file using a file output stream, ofstream.

Notice that the first element primes[0] is never used and we start elimination from 2 !

    #include <iostream>
    #include <vector>
    #include <thread>
    #include <fstream>
    #include <math.h>

    using namespace std;

    class Prime
    {
        int **primes;
        int N;
        public:
            Prime(int N)
            {
                this->N = N;

                primes = new int *[N];

                for(int i=0; i < N; i++)
                    primes[i] = new int[2],
                    primes[i][0] = i,
                    primes[i][1] = 1; // mark all as prime numbers
            }
            void eliminate(int p)
            {
                int i = p + p;
                while (i < N)
                    primes[i][1] = 0, // mark the multiplicies of p as not primes 
                    i+=p;
            }
            void display()
            {
                for(int i=1;i<N;i++)
                    {
                        if (primes[i][1] == 1)
                            cout<<primes[i][0]<<" " ;

                        if(i%10 == 0) cout<<endl;
                    }
                cout<<endl;
            }
            void save(string file)
            {
                ofstream fout(file);

                if(fout.is_open())
                    {
                        for(int i=1;i<N;i++)
                            {
                                if (primes[i][1] == 1)
                                    fout<<primes[i][0]<<" " ;

                                if(i%10 == 0) fout<<endl;
                            }
                        fout<<endl;

                    fout.close();    
                    }

                else
                    cout<<"cannot open file "<<file;
            }
    };

    int main()
    {

        vector<thread> v;

        int N;
        cout<<"genereate primes numbers less than N = ";
        cin >> N;

        Prime p(N);

        for(int i= 2; i < sqrt(N) ; i++)
            //p.eliminate(i);
            v.push_back( thread (&Prime::eliminate, ref(p), i ) );

        for (auto& th : v) th.join();    

        //p.display();
        p.save("primes.txt");

        return 0;
    }

Output:

genereate primes numbers less than N = 100
[primes.txt]
1 2 3 5 7
11 13 17 19
23 29
31 37
41 43 47
53 59
61 67
71 73 79
83 89
97