Thread: Sieve of eratosthenes in MPI. Internal loop only

Hello everyone,

I'm trying to parallelize with the mpi library and c++ the internal loop of the following sequential code (sieve of eratosthenes):

Code:

int main()
{
    int n = 40;
    int root = std::sqrt(n);
    int count = 0;

    bool* range = new bool[n];
    for (int i = 0; i < n; i++)
    {
        range[i] = true;
    }
    
    for (int i = 2; i <= root; i++)
    {
        if (range[i])
        {
            //Loop to be parallelized
            for (int j = i * i; j < n; j += i)
            {
                range[j] = false;
            }
        }
    }
    
    for (int k = 2; k < n; k++)
    {
        if (range[k])
        {
            count++;
        }
    }
    printf("Primes: %d", count);
}

I do not seek to parallelize the external loop, which although it would be a better solution, I must compare both performances.

In other words, I would like to parallelize the distribution of the elimination of multiples, which occurs when the range [j] takes the value of false

Thank you in advance.

It doesn't appear that you've asked a specific question but rather have asked for help generally? Could I ask: Are you expecting other people to write your code for you? I suggest that you at least show an attempt to find a solution - problem solving is at the heart of programming and quite frankly, there is no substitute for it.

I personally would start by refactoring your code so that the inner loop is in a function of its own - I think that on its own would aid with parallelization. I would then suggest you try reading more about MPI because the way you have asked your question would suggest you aren't that familiar with it (honestly, nor am I). After reading your question I spent 10 minutes or so reading this article (MPI Hello World * MPI Tutorial) and understood the basics, I would suggest you do something similar. E.g. Notice how in that example there is only 1 call to printf but 4 lines are printed? (Because of the parallelization). From what I can tell, the 'magic' happens between the MPI_Init and MPI_Finalize calls. If I were you, I would also look at some other examples found here: mpitutorial/tutorials at gh-pages * mpitutorial/mpitutorial * GitHub and try to learn from example code. At least that way you can attempt to solve the problem yourself and you can at least try to ask a more specific question if you are having problems. Sometimes its easier to solve concrete bugs when you've got something that mostly works rather than asking very general questions.. and you've asked a very general question.