# include <cstdlib>
# include <iostream>
# include <iomanip>
# include <ctime>
# include <mpi.h>

using namespace std;

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

//****************************************************************************80
//
//  Purpose:
//
//    PRIME computes the sum of the prime numbers between 2 and 100,000.
//
//  Discussion:
//
//    This program uses MPI to divide the work among P processes.
//
//    Each process prints out its partial result and wall clock time.
//
//    Process 0 prints the total and total time.
//
{
  int i;
  int id;
  int id_n_hi;
  int id_n_lo;
  int id_total;
  int j;
  int n_hi = 100000;
  int n_lo = 2;
  int p;
  bool prime;
  double wtime;
  double wtime_total;
  double wtime1;
  double wtime2;
  int total;
//
//  Initialize MPI.
//
  MPI::Init ( argc, argv );
//
//  Get the number of processes.
//
  p = MPI::COMM_WORLD.Get_size (  );
//
//  Determine this processes's rank.
//
  id = MPI::COMM_WORLD.Get_rank ( );
//
//  Work that only process 0 should do.
//
  if ( id == 0 )
  {
    cout << "\n";
    cout << "PRIME\n";
    cout << "  C++ version\n";
    cout << "  Number of processes = " << p << "\n";
    cout << "\n";
    cout << "        ID      N_LO      N_HI         TOTAL        TIME\n";
    cout << "\n";
    total = 0;
  }
//
//  Each process computes a portion of the sum.
//
  id_total = 0;

  id_n_lo = ( ( p - id     ) *   n_lo 
            + (     id     ) * ( n_hi + 1 ) ) 
            / ( p          );

  id_n_hi = ( ( p - id - 1 ) *   n_lo 
            + (     id + 1 ) * ( n_hi + 1 ) ) 
            / ( p          ) - 1;

  wtime1 = MPI::Wtime ( );

  for ( i = id_n_lo; i <= id_n_hi; i++ )
  {
    prime = true;

    for ( j = 2; j < i; j++ )
    {
      if ( i % j == 0 )
      {
        prime = false;
        break;
      }
    }
    if ( prime )
    {
      id_total = id_total + i;
    }
  }
  wtime2 = MPI::Wtime ( );
  wtime = wtime2 - wtime1;
  cout << "  " << setw(8) << id
       << "  " << setw(8) << id_n_lo
       << "  " << setw(8) << id_n_hi
       << "  " << setw(12) << id_total
       << "  " << setw(14) << wtime << "\n";
//
//  Use REDUCE to gather up the partial totals and send to process 0.
//  Use REDUCE to gather up the WALL CLOCK times and send to process 0.
//
  MPI::COMM_WORLD.Reduce ( &id_total, &total, 1, MPI::INT, MPI::SUM, 0 );
  MPI::COMM_WORLD.Reduce ( &wtime, &wtime_total, 1, MPI::DOUBLE, MPI::SUM, 0 );

  if ( id == 0 )
  {
    cout << "\n";
    cout << "  " << "   Total"
         << "  " << setw(8) << n_lo
         << "  " << setw(8) << n_hi
         << "  " << setw(12) << total
         << "  " << setw(14) << wtime << "\n";
  }

  MPI::Finalize ( );

  return 0;
}