Welcome to the fourm, Shuaizheng!

I don't know anything about MPI yet, but I know a bit about using the Sieve of Eratosthenes.

1) if you use calloc() to create your sieve array, you will get all zero's in it. Now reverse your logic (so all the non-primes are marked out with a one, instead). The advantage is that you only need a one dimension sieve array.

if(sieve[indexNumber] is 0), then the indexNumber is prime, as the for loop works forward.

2) you don't need to mark out duplicates of 2. They will be skipped. Assign sieve[0] to 1 since 1 is not prime. Start your for loop which checks for primality, at 3, and increment it by +=2.

Assign p[0] = 2;

Below is the ENTIRE block of code to mark the sieve[] and also, find all the primes, in my program:

SieveSize is a define as the largest prime number the program will find+1

pcnt is an int, and counts the number of primes found

it all serves as the index into the primes array named p[].

The second (inner) for loop, is my own math, because what I had before had far too many repeated values. It is accurate for < 86,028,000, but untested above that value.

Code:

for(i=3;i<SieveSize;i+=2) {
if(!s[i]) { //it's a prime
++pcnt;
p[pcnt]=i; //add the prime into the array of primes
//mark off all it's multiples in the sieve array
for(k=3,j = i*k;j<SieveSize;j=(i*(k+=2))) {
s[j] = 1;
}
}
}

If you look at the "fastest printing to a console" thread, KCfromNC has posted some VERY nice code for finding primes.