First MPI Assignment:   Due Monday 12/7/2015

/*

  A prime number is any number > 1 that's divisible only by 1 and itself.
  There are many sophisticated ways to test for primes.  A simple one is
  to test if the number is divisible by 2 or any odd number between
  3 and n/2.  

  Here is a conventional, 1-process implementation:
*/

int isprime(unsigned long long n)
{
  unsigned long long i;  
  if (n==2) return 1;
  if ((n<2) || (n%2 == 0)) return 0;
  for(i=3;i<=n/2 && ((n%i)>0);i+=2);
  return (i>n/2);
}


/*
    Is this algorithm a good candidate for parallel speedup?  You should
    show that it is by deriving the complexity of computation versus
    the complexity of communication.  Then you should implement a 
    multi-processor solution to demonstrate your hypothesis.

    Each process will be responsible for checking if the number is
    divisible by a range of values, and send the result back to the rank-0
    process.  For the final communication, when the results are
    gathered from each process, use MPI_REDUCE with operation MPI_LAND
    (logical and), instead of the normal send/receive operations.  
    MPI_REDUCE is similar to MPI_Bcast: all processes must call it.
    Read the description of this function in the textbook and online
    docs carefully.

    The C datatype unsigned long long (64 bit non-negative integer)
    corresponds to the MPI datatype MPI_UNSIGNED_LONG_LONG.  However,
    unlike the 'Writable' and 'Serializable' classes of Hadoop and RMI,
    MPI does not change the underlying binary representation: the name is
    only used for compatibility.  In fact, Beowulf clusters typically consist
    of identical machines, so even byte ordering (endian) conversions are
    not needed. 

    
    Here are some known large prime for you to test, others are easy to 
    look up.

    2147483647
    2147483629
    2147483587

    Also test your program on non-primes, and compare the answer with
    that returned by the conventional function above.  Compare the
    elapsed time of the conventional function and your multi-processor
    implementation.  You should see speed up for the large numbers above.

*/