# include <cstdlib>
# include <iostream>
# include <iomanip>
# include <ctime>

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 is very close to being an MPI program already.
//
//    The calculation has been split up among P processes, each of
//    which is given a range to work in, and each of which returns a
//    partial sum and CPU time.
//
//    Modify the program so that it runs under MPI.
//
{
  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 = 10;
  bool prime;
  double wtime;
  double wtime_total;
  double wtime1;
  double wtime2;
  int total;

  total = 0;
//
//  We pretend there are P processes.
//  We divide the range [N_LO,N_HI] into P roughly equal subintervals.
//  We ask process ID to check the ID-th subinterval and return the
//  total in that range.
//
  cout << "\n";
  cout << "PRIME\n";
  cout << "  C++ version\n";
  cout << "\n";
  cout << "        ID      N_LO      N_HI         TOTAL        TIME\n";
  cout << "\n";

  for ( id = 0; id < p; id++ )
  {
    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;
//
//  Begin the work done by one "process"
//
    t1 = ( double ) clock ( ) / ( double ) CLOCKS_PER_SEC;

    id_total = 0;
    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;
      }
    }

    total = total + id_total;

    cout << "  " << setw(8) << id
         << "  " << setw(8) << id_n_lo
         << "  " << setw(8) << id_n_hi
         << "  " << setw(12) << id_total << "\n";
//
//  End of work of one process.
//
  }
  cout << "\n";
  cout << "  " << "   Total"
       << "  " << setw(8) << n_lo
       << "  " << setw(8) << n_hi
       << "  " << setw(12) << total << "\n";
  return 0;
}