思路：
只保留奇数
(1)由输入的整数n确定存储奇数（不包括1）的数组大小：
n=(n%2==0)?(n/2-1):((n-1)/2);//n为存储奇数的数组大小，不包括基数1
(2)由数组大小n、进程号id和进程数p，确定每个进程负责的基数数组的第一个数、最后一个数和数组维度：
low_value = 3 + 2*(id*(n)/p);//进程的第一个数
high_value = 3 + 2*((id+1)*(n)/p-1);//进程的最后一个数
size = (high_value - low_value)/2 + 1; //进程处理的数组大小
(3)寻找奇数的第一个倍数的下标，经过反复思考，有如下规律：
if (prime * prime > low_value)
first = (prime * prime - low_value)/2;
else {
if (!(low_value % prime))
first = 0;
else
first=((prime-low_value%prime)%2==0)?((prime-low_value%prime)/2):((prime-low_value%prime+prime)/2);
}
code:
#include "mpi.h"
#include <math.h>
#include <stdio.h>
#define MIN(a,b) ((a)<(b)?(a):(b)) int main (int argc, char *argv[])
{
int count; /* Local prime count */
double elapsed_time; /* Parallel execution time */
int first; /* Index of first multiple */
int global_count; /* Global prime count */
int high_value; /* Highest value on this proc */
int i;
int id; /* Process ID number */
int index; /* Index of current prime */
int low_value; /* Lowest value on this proc */
char *marked; /* Portion of 2,...,'n' */
int n,m; /* Sieving from 2, ..., 'n' */
int p; /* Number of processes */
int proc0_size; /* Size of proc 0's subarray */
int prime; /* Current prime */
int size; /* Elements in 'marked' */ MPI_Init (&argc, &argv); /* Start the timer */ MPI_Comm_rank (MPI_COMM_WORLD, &id);
MPI_Comm_size (MPI_COMM_WORLD, &p);
MPI_Barrier(MPI_COMM_WORLD);
elapsed_time = -MPI_Wtime(); if (argc != ) {
if (!id) printf ("Command line: %s <m>\n", argv[]);
MPI_Finalize();
exit ();
} n = atoi(argv[]);
m=n;//
n=(n%==)?(n/-):((n-)/);//将输入的整数n转换为存储奇数的数组大小，不包括奇数1
//if (!id) printf ("Number of odd integers:%d Maximum value of odd integers:%d\n",n+1,3+2*(n-1));
if (n==) {//输入2时，输出1 prime，结束
if (!id) printf ("There are 1 prime less than or equal to %d\n",m);
MPI_Finalize();
exit ();
}
/* Figure out this process's share of the array, as
well as the integers represented by the first and
last array elements */ low_value = + *(id*(n)/p);//进程的第一个数
high_value = + *((id+)*(n)/p-);//进程的最后一个数
size = (high_value - low_value)/ + ; //进程处理的数组大小 /* Bail out if all the primes used for sieving are
not all held by process 0 */ proc0_size = (n-)/p; if (( + *(proc0_size-)) < (int) sqrt((double) (+*(n-)))) {//
if (!id) printf ("Too many processes\n");
MPI_Finalize();
exit ();
} /* Allocate this process's share of the array. */ marked = (char *) malloc (size); if (marked == NULL) {
printf ("Cannot allocate enough memory\n");
MPI_Finalize();
exit ();
} for (i = ; i < size; i++) marked[i] = ;
if (!id) index = ;
prime = ;//从素数3开始
do {
//确定奇数的第一个倍数的下标
if (prime * prime > low_value)
first = (prime * prime - low_value)/;
else {
if (!(low_value % prime))
first = ;
else
first=((prime-low_value%prime)%==)?((prime-low_value%prime)/):((prime-low_value%prime+prime)/);
} for (i = first; i < size; i += prime) marked[i] = ;
if (!id) {
while (marked[++index]);
prime = *index + ;//下一个未被标记的素数
}
if (p > ) MPI_Bcast (&prime, , MPI_INT, , MPI_COMM_WORLD);
} while (prime * prime <= +*(n-));// count = ;
for (i = ; i < size; i++)
if (!marked[i]) count++;
if (p > ) MPI_Reduce (&count, &global_count, , MPI_INT, MPI_SUM,
, MPI_COMM_WORLD); /* Stop the timer */ elapsed_time += MPI_Wtime(); /* Print the results */ if (!id) {
printf ("There are %d primes less than or equal to %d\n",
global_count+, m);//前面程序是从素数3开始标记，忽略了素数2，所以素数个数要加1
printf ("SIEVE (%d) %10.6f\n", p, elapsed_time);
}
MPI_Finalize ();
return ;
}