/* Programming Project #1
 * Operating Systems, Spring 2005*/
#include <pthread.h>
#include <stdio.h>
#include <math.h>

/* This program successively tests integers for prime numbers.  Return the Nth
prime number, where N is the value pointed to by *ARG. */

void * compute_prime (void * params)
{

  int candidate = * ((int*) params);

  int factor;
  int is_prime = 1;
  int upper_limit = (int) sqrt(candidate); /*You need only test up to sqrt(x)
                                                      divisiors of x */

  /* Test primality by successive division */
  for (factor = 2; factor <= upper_limit; ++factor)
  {
      if (candidate % factor == 0)
      {
        is_prime = 0; /*false*/
        break;
      }
  }
  return (int*)is_prime;
}

int main () {
  pthread_t thread1, thread2, thread3, thread4;
  int prime1, prime2, prime3, prime4;
  int isPrime1, isPrime2, isPrime3, isPrime4;

  int which_prime     =    10;
  int factor          =    3;            //Amount of concurrent threads we are using
  int loop_control1   =    1;            //Counter for first loop
  int loop_control2   =    0;            //Counter for second loop
  int finished        = which_prime - (factor +2); //want to do the last (factor) on our own, plus 1 and 2 are given
  int answer;

  //This solution breaks down for small cases: hard-coded for "sanity check"
  if (which_prime == 2)
          printf("The %dth prime is 2.\n", which_prime);
  if (which_prime == 3)
          printf("The %dth prime is 5.\n", which_prime);
  if (which_prime == 4)
          printf("The %dth prime is 7.\n", which_prime);
  if (which_prime == 5)
          printf("The %dth prime is 11.\n", which_prime);

  while(1)
  {
        //Hard coded for small case "sanity check"
        if (which_prime < 6)
                break;

        prime1 = factor * loop_control1;
        prime2 = prime1 +1;
        prime3 = prime2 +1;

        /* Start 3 threads, each returns if it's number is prime*/
        pthread_create(&thread1, NULL, &compute_prime, &prime1);
        pthread_create(&thread2, NULL, &compute_prime, &prime2);
        pthread_create(&thread3, NULL, &compute_prime, &prime3);

        /* Wait for all threads to complete, and grab the values when they are done */
        pthread_join(thread1, (void*) &isPrime1);
        pthread_join(thread2, (void*) &isPrime2);
        pthread_join(thread3, (void*) &isPrime3);
        if (isPrime1)
        {
                --finished;
                if (finished == 0)
                {
                        answer = prime1;
                        break;
                }
        }

        if (isPrime2)
        {
                --finished;
                if (finished == 0)
                {
                        answer = prime2;
                        break;
                }
        }
        if (isPrime3)
        {
                --finished;
                if (finished == 0)
                {
                        answer = prime3;
                        break;
                }
        }

        ++loop_control1;
  }

  //Exactly 3 are left: test each number after what last loop gave us,
  //but only increment for loop's counter if one is found
  loop_control2 = factor; //need to find the last (factor) primes
  while (1)
  {
          //Hard coded for small case "sanity check"
          if (which_prime < 6)
                break;

          answer = answer + 1;
          pthread_create(&thread4, NULL, &compute_prime, &answer);
          pthread_join(thread4, (void*) &isPrime4);

          if (isPrime4)
          {
                  --loop_control2;
                  if (loop_control2 == 0)
                        break;
          }
  }
  //after this, answer should be the correct prime
  /* Print the largest prime that it computed */
  //Hard coded for small case "sanity check"
  if (which_prime > 5)
        printf("The %dth prime number computed is %d.\n", which_prime, answer);
  return 0;
}