program main

c*********************************************************************72
c
cc PRIME counts the prime numbers between 2 and 100,000.
c
c  Discussion:
c
c    This program uses MPI to divide the work among P processes.
c
c    Process 0 prints the total and total time.
c
      include 'mpif.h'

      implicit none

      integer i
      integer id
      integer id_n_hi
      integer id_n_lo
      integer id_total
      integer ierr
      integer j
      integer n_hi
      parameter ( n_hi = 100000 )
      integer n_lo
      parameter ( n_lo = 2 )
      integer p
      logical prime
      double precision wtime
      integer total
c
c  Initialize MPI.
c
      call MPI_Init ( ierr )
c
c  Get this process's ID.
c
      call MPI_Comm_rank ( MPI_COMM_WORLD, id, ierr )
c
c  Find out how many processes are available.
c
      call MPI_Comm_size ( MPI_COMM_WORLD, p, ierr )
c
c  Work that only process 0 should do.
c
      if ( id .eq. 0 ) then

        write ( *, '(a)' ) ' '
        write ( *, '(a)' ) 'PRIME'
        write ( *, '(a)' ) '  FORTRAN77 version'
        write ( *, '(a,i8)' ) '  Number of processes = ', p

        write ( *, '(a)' ) ' '
        write ( *, '(a)' ) 
     &    '        ID      N_LO      N_HI         TOTAL        TIME'
        write ( *, '(a)' ) ' '

        total = 0
        wtime = MPI_Wtime ( )

      end if
c
c  Each process computes a portion of the sum.
c
      id_total = 0
      id_time = 0.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
c
c  Begin the work done by one "process"
c
      do i = id_n_lo, id_n_hi

        prime = .true.

        do j = 2, i - 1
          if ( mod ( i, j ) .eq. 0 ) then
            prime = .false.
            go to 10
          end if
        end do

        if ( prime ) then
          id_total = id_total + 1
        end if

10      continue

      end do

      write ( *, '(2x,i8,2x,i8,2x,i8,2x,i12)' ) 
     &  id, id_n_lo, id_n_hi, id_total
c
c  Use REDUCE to gather up the partial totals and send to process 0.
c  Use REDUCE to gather up the WALL CLOCK times and send to process 0.
c
      call MPI_Reduce ( id_total, total, 1, MPI_INTEGER, MPI_SUM, 0, 
     &  MPI_COMM_WORLD, ierr )

      if ( id .eq. 0 ) then
        wtime = MPI_Wtime ( ) - wtime
        write ( *, '(a)' ) ' '
        write ( *, '(2x,a8,2x,i8,2x,i8,2x,i12,2x,g14.6)' ) 
     &    '   Total', n_lo, n_hi, total, wtime
      end if

      call MPI_Finalize ( ierr )

      return
      end