PRIME_NUMBER_MPI
Count Primes Using MPI

PRIME_NUMBER_MPI is a C++ program which counts the number of primes between 1 and N, using MPI to carry out the calculation in parallel.

The algorithm is completely naive. For each integer I, it simply checks whether any smaller J evenly divides it. The total amount of work for a given N is thus roughly proportional to 1/2*N^2.

This program is mainly a starting point for investigations into parallelization.

Here are the counts of the number of primes for some selected values of N:

N	Pi(N), Number of Primes
1	0
2	1
4	2
8	4
16	6
32	11
64	18
128	31
256	54
512	97
1024	172
2048	309
4096	564
8192	1028
16384	1900
32768	3512
65536	6542
131072	12251

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Related Data and Programs:

HEAT_MPI is a C++ program which solves the 1D Time Dependent Heat Equation using MPI.

MPI C++ programs which illustrate the use of the MPI application program interface for carrying out parallel computations in a distributed memory environment.

MPI_STUBS is a C++ library which contains "stub" MPI routines, allowing a user to compile, load, and possibly run an MPI program on a serial machine.

MPI_SYSX, C++ programs which illustrate the use of PBS scripts for submitting MPI jobs on System X.

PRIME_NUMBER is a C++ program which counts the number of primes between 1 and N.

PRIME_NUMBER_OPEN_MP is a C++ program which counts the number of primes between 1 and N, using OpenMP for parallel execution.

PRIME_NUMBER_MPI is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version.

PRIME_NUMBER_PARALLEL is a MATLAB program which counts the number of primes between 1 and N; it runs in parallel using MATLAB's "parfor" facility.

QUAD_MPI is a C++ program which approximates an integral using a quadrature rule, and carries out the computation in parallel using MPI.

RANDOM_MPI, a C++ program which demonstrates one way to generate the same sequence of random numbers for both sequential execution and parallel execution under MPI.

SATISFIABILITY_MPI is a C++ program which demonstrates, for a particular circuit, an exhaustive search for solutions of the circuit satisfiability problem, using MPI to carry out the calculation in parallel.

Reference:

1. Eratosthenes,
   A Method For Finding Prime Numbers,
   Papyrus 487.

Source Code:

• prime_number_mpi.C, the source code.

Examples and Tests:

• prime_number_mpi.sh, a PBS script which is suitable for running the program on System X.
• prime_number_mpi_output_nt4.txt, the output file for 4 processes (2 nodes, 2 processes per node).

List of Routines:

• MAIN is the main program for PRIME_NUMBER_MPI.
• PRIME_NUMBER returns the number of primes between 1 and N.

You can go up one level to the C++ source codes.