#include <stdio.h>
#include <omp.h>
#include <winsock.h>
#define N 10000000
#define TRUE 1
#define FALSE 0
#define Square(x) ((x)*(x))

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

  if (WSAStartup(MAKEWORD(1, 1), &WsaDat) != 0)
    printf("WSA Initialization failed.");
  if (gethostname(host,sizeof(host)) == SOCKET_ERROR)
   {
    printf("ERROR getting hostname\n");
    exit(0);
   }
  //Determine the number of physical processors
  procs = omp_get_num_procs();
  printf("%s has %d processors\n",host,procs);
  //Determine how many threads 
  // may be set by OMP_NUM_THREADS environment variable
  printf("OMP_NUM_THREADS = %d\n",omp_get_max_threads());
  printf("OMP_DYNAMIC = ");
  if (!omp_get_dynamic()) 
   {
    printf("FALSE\n");
    if (argc != 2) threads = omp_get_max_threads(); 
    else threads = atoi(argv[1]);
    //Set the number of threads 
    printf("Setting NUM_THREADS = %d\n",threads);
    omp_set_num_threads(threads);
   }
   a = (int *) malloc(N * 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 (Square(k) <= N)
   {
    // a. Mark all multiples of k between k^2 and N
     #pragma omp parallel for
     for (i=Square(k); i<=N; i++)
     {
      if ((i % k) == 0) { 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("%.2f seconds\n",t2-t1);
  // 4. The unmarked numbers are primes
  for (i=2;i<=N;i++) { if (a[i]) { printf("%d\n",i); } }
 }