# include <stdlib.h>
# include <stdio.h>
# include <time.h>

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

/******************************************************************************/
/*
  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;
  int 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.
*/
  printf ( "\n" );
  printf ( "PRIME:\n" );
  printf ( "  C version\n" );
  printf ( "\n" );
  printf ( "        ID      N_LO      N_HI         TOTAL        TIME\n" );
  printf ( "\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;

    id_total = 0;
    for ( i = id_n_lo; i <= id_n_hi; i++ )
    {
      prime = 1;

      for ( j = 2; j < i; j++ )
      {
        if ( i % j == 0 )
        {
          prime = 0;
          break;
        }
      }
      if ( prime )
      {
        id_total = id_total + i;
      }
    }

    total = total + id_total;

    printf ( "  %8d  %8d  %8d  %12d\n", id, id_n_lo, id_n_hi, id_total );

  }
  printf ( "\n" );
  printf ( "     Total  %8d  %8d  %12d\n", n_lo, n_hi, total );
  return 0;
}