/*/////////////////////////////////////////////////////////////////////////////
//
// File name : sieve.c
// Author    : Nissa Osheim
// Date      : 2010/19/10
// Desc      : Finds the primes up to N
//
/////////////////////////////////////////////////////////////////////////////*/


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "timer.h"

#define MAX(x,y)   ((x)>(y) ? (x) : (y) )
#define MIN(x,y)   ((x)>(y) ? (y) : (x) )

#define A(i,j)     A[(i)*M+j]
#define b(i)       b[i]
#define c(i)       c[i]

int main(int argc, char **argv) {

   long N  = 100000;

   char *mark;

   int   size;
   int   curr;
   int   i, j;
   int   count;

   /* Time */

   double time;

   if ( argc > 1 ) N  = atoi(argv[1]);

   /* Start Timer */

   initialize_timer ();
   start_timer();

   size = N*sizeof(char);
   mark = (char *)malloc(size);

   for (i=2; i<N; i=i+1){
     mark[i]=0;
   }

   curr=2;       /*first prime*/
   while (curr<sqrt(N)){
     for (i=curr+curr; i<N; i=i+curr){
	   mark[i]=1;
	 }
	 curr=curr+1;
	 while (curr<N && mark[curr]==1){
	   curr=curr+1;
	 }
   }
     
   /* stop timer */
   stop_timer();
   time=elapsed_time ();

   /*number of primes*/
   count = 0;
   for(i = 2; i < N; i++){
        if(mark[i] == 0) count++;
   }
   printf("There are %d primes less than %d\n", count, N);
   /* print results */
   printf("First three primes:");
   j = 0;
   for ( i=2 ; i < N && j < 3; i++ ) {
      if (mark[i]==0){
            printf("%d ", i);
            ++j;
      }
   }
   printf("\n");

   printf("Last three primes:");
   j = 0;
   for (i = N - 1; i > 1 && j < 3; i--){
     if (mark[i]==0){
        printf("%d ", i);
        j++;
     }
   }
   printf("\n");


   printf("elapsed time = %lf (sec)\n", time);
   
   free(mark);
   return 0;
}