PRIME_NUMBER_MPI
Count Primes Using MPI

PRIME_NUMBER_MPI is a FORTRAN77 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 FORTRAN77 program which solves the 1D Time Dependent Heat Equation using MPI.

MPI FORTRAN77 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 FORTRAN77 library which contains "stub" MPI routines, allowing a user to compile, load, and possibly run an MPI program on a serial machine.

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

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

PRIME_NUMBER_OPEN_MP is a FORTRAN77 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 FORTRAN77 program which approximates an integral using a quadrature rule, and carries out the computation in parallel using MPI.

RANDOM_MPI, a FORTRAN77 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 FORTRAN77 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.f, the source code.

Examples and Tests:

The MPI_STUBS library can sometimes be used as a quick check on a code. It can be used on a computer system where MPI is not available. It provides dummy versions of many of the MPI functions, and for simple computations with a single process may actually compute a reasonable answer.

• prime_number_mpi_stubs.csh, a C shell script which compiles and runs the program with the dummy MPI_STUBS library.
• prime_number_mpi_stubs_output_nt1.txt, the output file for 1 process.

• 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 FORTRAN77 source codes.