# include "mpi.h"
# include <stdlib.h>
# include <stdio.h>
# include <math.h>
# include <time.h>

double cpu_time ( void ) {
  double value;

  value = ( double ) clock ( )
        / ( double ) CLOCKS_PER_SEC;

  return value;
}

int prime_number ( int n ) {
  int i;
  int j;
  int prime;
  int total;

  total = 0;

  for ( i = 2; i <= n; i++ )
  {
    prime = 1;
    for ( j = 2; j < i; j++ )
    {
      if ( ( i % j ) == 0 )
      {
        prime = 0;
        break;
      }
    }
    total = total + prime;
  }
  return total;
}

int prime_numberp ( int n ) {
  int i;
  int j;
  int prime;
  int total, local, start;
  int rank, size, master = 0;

  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);

  MPI_Recv(&start, 1, MPI_INT, master, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

  total = 0;
  //printf ("Start for thread %d is %d", rank, start);

  for ( i = start; i <= n; i = i + size - 1)
  {
    prime = 1;
    for ( j = 2; j < i; j++ )
    {
      if ( ( i % j ) == 0 )
      {
        prime = 0;
        break;
      }
    }
    total = total + prime;
  }
  return total;
}

void timestamp ( void ){
# define TIME_SIZE 40

  static char time_buffer[TIME_SIZE];
  const struct tm *tm;
  size_t len;
  time_t now;

  now = time ( NULL );
  tm = localtime ( &now );

  len = strftime ( time_buffer, TIME_SIZE, "%d %B %Y %I:%M:%S %p", tm );

  printf ( "%s\n", time_buffer );

  return;
# undef TIME_SIZE
}

void test ( int n_lo, int n_hi, int n_factor );
void testp ( int n_lo, int n_hi, int n_factor );

int main (int argc, char *argv[] ) {
  MPI_Init(NULL, NULL);
  int n_factor;
  int n_hi;
  int n_lo;
  int rank, size, master = 0;
  double ctimes, ctimep;

  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);

  if (rank == master) {
      timestamp ( );
      printf ( "\n" );
      printf ( "PRIME TEST SEQUENTIAL\n" );

      if ( argc !=4 ) {
        n_lo = 1;
        n_hi = 131072;
        n_factor = 2;
      } else {
        n_lo = atoi(argv[1]);
        n_hi = atoi(argv[2]);
        n_factor = atoi(argv[3]);
      }
      ctimes = cpu_time ( );
      test ( n_lo, n_hi, n_factor );
      ctimes = cpu_time ( ) - ctimes;
      printf ( "\n" );
      printf ( "PRIME TEST PARALLEL\n" );
      ctimep = cpu_time ( );
  }
  testp ( n_lo, n_hi, n_factor );


  if (rank == master) {
      ctimep = cpu_time ( ) - ctimep;
      printf("\n============================================\n");
      printf("SEQUENTIAL - Execution time: %f\n", ctimes);
      printf("PARALLEL - Execution time: %f\n", ctimep);
      printf("\n============================================\n");
      printf ( "\n" );
      printf ( "PRIME_TEST\n" );
      printf ( "  Normal end of execution.\n" );
      printf ( "\n" );
      timestamp ( );


  }
  MPI_Finalize();
  return 0;
}

void test ( int n_lo, int n_hi, int n_factor ) {
  int i;
  int n;
  int primes;
  double ctime;

  printf ( "\n" );
  printf ( "SEQUENTIAL EXECUTION\n" );
  printf ( "  Call PRIME_NUMBER to count the primes from 1 to N.\n" );
  printf ( "\n" );
  printf ( "         N        Pi          Time\n" );
  printf ( "\n" );

  n = n_lo;

  while ( n <= n_hi )
  {
    ctime = cpu_time ( );

    primes = prime_number ( n );

    ctime = cpu_time ( ) - ctime;

    printf ( "  %8d  %8d  %14f\n", n, primes, ctime );
    n = n * n_factor;
  }

  return;
}

void testp ( int n_lo, int n_hi, int n_factor ) {
  int i;
  int n;
  int primes;
  double ctime;
  int rank, size, master = 0;
  int local;
  int start;
  int flag;
  int loop = 1;

  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);

  if (rank == master) {
      printf ( "\n" );
      printf ( "PARALLEL EXECUTION\n" );
      printf ( "  Call PRIME_NUMBER to count the primes from 1 to N.\n" );
      printf ( "\n" );
      printf ( "         N        Pi          Time\n" );
      printf ( "\n" );



    n = n_lo;
  }


  while ( loop )
  {
    if (rank == master){
        ctime = cpu_time ( );

        for (i=1; i<size; i++) {
            MPI_Send(&flag, 1, MPI_INT, i, 0, MPI_COMM_WORLD);

            if (flag) {
                start = i+1;

                MPI_Send(&n, 1, MPI_INT, i, 0, MPI_COMM_WORLD);

                MPI_Send(&start, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
            }
            else {
                loop = 0;
                MPI_Send(&loop, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
            }
        }
    }

    if (rank != master) {
        MPI_Recv(&flag, 1, MPI_INT, master, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        if (flag) {
            MPI_Recv(&n, 1, MPI_INT, master, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

            local = prime_numberp ( n );

            MPI_Send(&local, 1, MPI_INT, master, 0, MPI_COMM_WORLD);
        }
        else MPI_Recv(&loop, 1, MPI_INT, master, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    }

    if (rank == master && flag) {
        primes = 0;

        for (i = 1; i < size; i++) {
            MPI_Recv( &local, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, MPI_STATUS_IGNORE );

            primes = primes + local;
        }

        ctime = cpu_time ( ) - ctime;

        printf ( "  %8d  %8d  %14f\n", n, primes, ctime );

    n = n * n_factor;
    if (n > n_hi) flag = 0;
    }

  }

  return;
}