Question

Write an MPI program, countprimes which will count the number of prime numbers in the numbers from 1 to n inclusive where n is a long integer. The value for n which can be set in the program using a constant should be 50,000. Each process will test its share of the cases. Each process should print out any primes that it finds in a readable manner indicating which process found it and the actual prime. The master process should end with printing a total for the count of the number of primes and the total amount of time taken to find all the primes. Please follow the following instructions carefully before submitting your work: Before submission, make sure you clean up the directories so that no miscellaneous files are kept around in the submission. (Grade would be deducted if useless files are found in the homework directories.) Include the source code and the Makefile in the submission.

Answer 1

C Program using MPI for the given Question:

#include <math.h>

#include <mpi.h>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

int main(int argc, char *argv[] );

int prime_number (int n, int id, int p);

void timestamp ();

int main (int argc , char *argv[] )

//purpose: main is the main program for PRIME_MPI.

{

int i,id,err,n, n_factor, n_hi, n_lo, p, primes, primes_part;

double wtime;

n_lo = 1;

n_hi = 262144;

n_factor = 2;

//Initialize MPI.

ierr = MPI_init ( &argc, &argv );

//Get the number of proesses.

ierr = MPI_comm_size ( MPI_COMM_WORLD, &p );

//determine this processes's rank.

ierr = MPI_COMM_RANK (MPI_COMM_WORLD, &id );

if ( id == 0){

timestamp ( );

printf ( "\n" );

printf ( "PRIME_MPI\n" );

printf ( " C/MPI version\n" );

printf ( "\n" );

printf ( "An MPI example program to count number of primes.\n" );

printf ( "The numberof processes is %d\n", p );

printf ( "\n" );

printf ( " N pi Time\n" );

printf ( "\n" );

}

n = n_lo;

while ( n <= n_hi ){

if ( id == 0){

wtime = MPI_Wtime ( );

}

ierr = MPI_Bcast ( &n, 1, MPI_INT, 0, MPI_COMM_WORLD );

primes_part = prime-number ( n, id, p );

ierr = MPI_Reduce ( &primes_part, &primes, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD );

if ( id == 0 ){

wtime = MPI_Wtime ( ) - wtime;

printf ( " %8d %8d %14f\n", n, primes, wtime );

}

n = n * n_factor;

}

//Terminate MPI.

ierr = MPI_Finalize ( );

//Terminate.

if ( id == 0 ){

printf ( "\n" );

printf ( "PRIME_MPI - Master process: \n");

printf ( " Normal end of execution. \n");

timestamp ( );

}

return 0;

}

{

int i;

int j;

int prime;

int total;

total = 0;

for ( i = 2 + id; i <= n; i = i + p ){

prime = 1;

for ( j = 2; j < i; j ++ ){

if ( ( i% j ) == 0 ){

prime = 0;

break;

}

}

total = total + prime;

}

return total;

}b