#include <stdio.h>
#include <omp.h>
#define N 100000000
#define TRUE 1
#define FALSE 0

int main(int argc, char **argv )
{
  char host[80];
  int *a;
  int i, k, threads, pcount;
  double t1, t2;
  int found;

  /* Set number of threads equal to argv[1] if present */
  if (argc > 1)
    {
      threads = atoi(argv[1]);
      if (omp_get_dynamic())
        {
          omp_set_dynamic(0);
          printf("called omp_set_dynamic(0)\n");
        }
      omp_set_num_threads(threads);
    }
  printf("%d threads max\n",omp_get_max_threads());

  a = (int *) malloc((N+1) * sizeof(int));
  // 1. create a list of natural numbers 2, 3, 4, ... none of which is marked.
  for (i=2;i<=N;i++) a[i] = 1;
  // 2. Set k = 2, the first unmarked number on the list.
  k = 2;

  t1 = omp_get_wtime();
  // 3. Repeat
  while (k*k <= N)
    {
      // a. Mark all multiples of k between k^2 and N
      #pragma omp parallel for
      for (i=k*k; i<=N; i+=k) a[i] = 0;
      // b. Find the smallest number greater than k that is unmarked 
      //    and set k to this new value until k^2 > N
      found = FALSE;
      for (i=k+1;!found;i++)
      {
        if (a[i]){ k = i; found = TRUE; }
      }
    }
  t2 = omp_get_wtime(); 
  printf("%.6f seconds\n",t2-t1);

  // 4. The unmarked numbers are primes
  pcount = 0;
  for (i=2;i<=N;i++)
    {
      if( a[i] )
        { 
          pcount++;
          // printf("%d\n",i);
        }
    }
  printf("%d primes between 0 and %d\n",pcount,N);
}