Eratosthenes sieve and MPI I wrote this sieve of Eratosthenes with MPI, but I'm not sure if it's good enough. Should I use MPI_Scatter and MPI_Gather instead of collecting arrays of separate processes in the root process?

Also, I'm not sure if I call 

printArray(myArray, (N/size)-1);


right, where myArray is an array of pointers. GCC gives a warning at this point. 

#include "mpi.h"
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;math.h&gt;
#include &lt;time.h&gt;

#define N 60

int main(int argc, char *argv[])
{
long timeCPU;
int rank, size, k, i, v, n, scatterSize;
int **tmpArray, *myArray, firstElement, lastElement;

MPI_Init(&amp;argc,&amp;argv);

MPI_Comm_rank(MPI_COMM_WORLD, &amp;rank);
MPI_Comm_size(MPI_COMM_WORLD, &amp;size);

if(N%size != 0)
{
    MPI_Finalize();
    printf("ERROR!");
    exit(0);
}

firstElement = (rank*N)/size;
lastElement = floor(((rank+1)*N)/size);
myArray = (int*) (malloc(((N/size)-1)*sizeof(int)));

for(i=0, v=firstElement+2; i&lt;=(N/size)-1; i++, v++)
{
    myArray[i] = v;
}
    printArray(myArray, (N/size)-1);
/* All processes have to execute above code first */
MPI_Barrier(MPI_COMM_WORLD);

k = 2;

do
{
    markMultiples(k, myArray, lastElement-firstElement);
    k = nextNumber(k, myArray, lastElement-firstElement);
    MPI_Bcast(&amp;k, 1, MPI_INT, 0, MPI_COMM_WORLD);
}
while(k*k &lt;=N);

MPI_Send(myArray, (N/size)-1, MPI_INT, 0, 50, MPI_COMM_WORLD);

MPI_Barrier(MPI_COMM_WORLD);

if (rank == 0)
{
    // Initialize 2D array
    tmpArray = (int**) (malloc(size*sizeof(int)));
    for(i=0;i&lt;size;i++)
    {
        tmpArray[i] = (int*) (malloc(((N/size)-1)*sizeof(int)));
    }

    // Gather from every process his own array
    for (i=0; i&lt;size;i++)
    {
        MPI_Recv(tmpArray[i], (N/size)-1, MPI_INT, i, 50, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        printArray(tmpArray[i], (N/size)-1);
        printf("-----------------------------------------\n");
    }

    // Build 1d array with primes - TODO

}

//printArray(array, lastElement-firstElement);
free(myArray);
MPI_Finalize();
return 0;
}

int nextNumber(int k, int *array, int n)
{
int i;

for(i=0; i&lt;=n; i++)
{
    if(array[i] &gt; k)
        return array[i];
}
return -1;
}

void markMultiples(int k, int *array, int n)
{
int i;

for (i=0; i&lt;=n; i++)
{
    if(array[i] % k == 0 &amp;&amp; array[i] != k)
    {
        array[i] = -1;
    }
}
}

void printArray(int *array, int n)
{
int i;

for(i=0; i&lt;=n; i++)
{
    printf("array[%d] = %d\n", i, array[i]);
}
}
Since you tagged this question c++ I assume you would like a C++ approach also.

I would suggest using std::vector&lt;int&gt; rather than an int* and malloc. Using the vector will give you a number of useful advantages over a normal pointer, for example, memory management is greatly simplified, and there is no need to worry about how big an int is. With vector, the order of all elements is guaranteed to be contiguous.

#include &lt;algorithm&gt;
#include &lt;functional&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;

int nextNumber(int k, const std::vector&lt;int&gt; &amp;array, int n)
{
    std::vector&lt;int&gt;::iterator i = std::find_if(array.begin(), array.begin() + n, std::bind2nd(std::greater&lt;int&gt;(), k));

    return (i == array.end() ? -1 : *i);
}

bool isMultiple(int a, int b)
{
    return (a % k == 0) &amp;&amp; (a != k);
}

void markMultiples(int k, std::vector&lt;int&gt; &amp;array, int n)
{
    std::replace_if(array.begin(), array.begin() + n, std::bind2nd(std::ptr_fun(isMultiple), k), -1);
}


void printArray(const std::vector&lt;int&gt; &amp;array)
{
    for(int i = 0; i &lt; array.size(); i++)
        std::cout &lt;&lt; "array[" &lt;&lt; i &lt;&lt; "] = " &lt;&lt; array[i] &lt;&lt; std::endl;
}


Disclaimer:

I am not very good at C++, so you may want to take this advice with a teaspoon of salt.