PRIME_MPI
Count Primes Using MPI


PRIME_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.

The latest versions of MPI no longer support the special C++ MPI bindings, so the examples given here have reverted to using the C MPI bindings.

Licensing:

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

Languages:

PRIME_MPI is available in a C version and a C++ version and a FORTRAN90 version and a Python version.

Related Data and Programs:

COMMUNICATOR_MPI, a C++ program which creates new communicators involving a subset of initial set of MPI processes in the default communicator MPI_COMM_WORLD.

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

HELLO_MPI, a C++ program which prints out "Hello, world!" using the MPI parallel programming environment.

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

MULTITASK_MPI, a C++ program which demonstrates how to "multitask", that is, to execute several unrelated and distinct tasks simultaneously, using MPI for parallel execution.

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

PRIME_SERIAL, a C++ program which counts the number of primes between 1 and N, intended as a starting point for the creation of a parallel version.

QUAD_MPI, 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.

RING_MPI, a C++ program which uses the MPI parallel programming environment, and measures the time necessary to copy a set of data around a ring of processes.

SATISFY_MPI, 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.

SEARCH_MPI, a C++ program which searches integers between A and B for a value J such that F(J) = C, using MPI for parallel execution.

WAVE_MPI, a C++ program which uses finite differences and MPI to estimate a solution to the wave equation.

Reference:

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

Source Code:

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


Last revised on 24 October 2011.