#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef enum{False,True} Boolean;

#define Trace_malloc 0

unsigned Size_mem() {
   unsigned int Alloc_amount = 0x1ff_ffff, /* 32 mb. */
   		Sum = 0;
   void try() {
      void *p;
      do {
         p = malloc(Alloc_amount);
         Alloc_amount = Alloc_amount / 2;
      } while (p == 0 && Alloc_amount > 256);  
      if (Trace_malloc) printf("Malloc-ed %d: %x\n",Alloc_amount*2,p);   
      if (p != 0) {
      	 Sum += Alloc_amount*2;
         if (Alloc_amount > 256) try();
         }
      if (p != 0) free(p);
      }
   try();
   return Sum;
   }    

char YesNo(char *msg) {
   char response;
   printf("%s (y/n)?",msg);
   scanf(" %c",&response);
   return response == 'y' || response == 'Y';
   } 

void print_banner() {
   int i;
	printf("\t\311");for(i=0;i<58;i++) printf("\315");printf("\273\n");
	printf("\t\272                   *MIGHTY* SIEVE!!!                      \272\n");
	printf("\t\314");for(i=0;i<58;i++) printf("\315");printf("\271\n");
	printf("\t\272  This program computes the primes up to the number you   \272\n");
	printf("\t\272  specify by using the sieve of Eratosthenes.  An array   \272\n");
	printf("\t\272  of booleans is dynamically allocated from  the  mega-   \272\n");
	printf("\t\272  bytes  available  under  the 32-bit adddress space of   \272\n");
	printf("\t\272  80386 protected mode.  The primes  are  computed  and   \272\n");
	printf("\t\272  then printed if you wish.                               \272\n");
	printf("\t\272  (Make sure you check each one; the computer might make  \272\n");
	printf("\t\272  a mistake!)                                             \272\n");
	printf("\t\310");for(i=0;i<58;i++) printf("\315");printf("\274\n");
   }

void main (int argc, char** argv) {
   int Size;
   Boolean *Primes;
   void init() {
#     define DEFAULT 16383
      /* Get the parameters. */
      /* If one or more arguments, assume Size = 8190 (the standard sieve). */
      if (argc > 1) Size = DEFAULT;
      else {
      L: printf("Enter the highest number that you wish tested for primality.\n"
      		"Enter 0 for the default of %d.\n"
                "Now enter your number:",DEFAULT,argv);
      	 scanf("%d",&Size);
      	 if (Size == 0) Size = DEFAULT;
      	 if (Size <= 1*2+3) {
      	    printf("Sorry, please try something a little bigger.\n");
      	    goto L;
      	    }
         }
      Size = (Size-3)/2;
   L2:printf("\nAllocating an array of %d elements...\n", Size+1); 
      Primes = (Boolean *) malloc(Size+1);
      if (Trace_malloc) printf("Malloc-ed %d: %x\n",Size+1,Primes);
      if (Primes == 0) {
      	 printf("Sorry, I don't seem to have that much memory...hang on...\n");
      	 printf("I seem to be able to allocate up to %d bytes for my array.\n",
      	 	Size = Size_mem());
      	 Size--;        /* In case we allocate; match what we print. */
      	 if (YesNo("Do you want me to use that much")) goto L2;
      	 else goto L;
      	 }
      }
   int Count,iter;
   /* The program currently computes the primes only once.		*/
   /* For a more time-consuming test, change ITERATIONS to a higher	*/
   /* value.								*/
#  define ITERATIONS 1
   print_banner();   
   init();

   printf("\nBegin computation of primes...\n");
   long start_time = clock();
   for (iter = 1; iter <= ITERATIONS; iter++) {
      int I,Prime,K;
      Count = 0;
      _fill_char(&Primes[0],Size,1);
      /* for (I = 0; I <= Size; I++) Primes[I] = True; */
      for (I = 0; I <= Size; I++)  
         if (Primes[I]) {
	    Prime = 2*I+3;
	    K = I+Prime;
	    while (K <= Size) {
	       Primes[K] = False;
	       K += Prime;
	       }
	    Count++;
            }
      }

   if (start_time != 0) 
      printf("You made me work for %d 1/%dths of a second.\n\n",
   		clock()-start_time, CLOCKS_PER_SEC);
   printf("There are %d primes between 3 and %d:\n",Count,2*Size+3);
   if (ITERATIONS != 1) printf("(I computed them %d times.)\n",ITERATIONS);		
   if (YesNo("Do you want to see them")) {
      register int I;	
      for (I = 0; I <= Size; I++)
         if (Primes[I]) printf("%7d ",2*I+3);
      }   
   printf("\nEnd of sieve program.\n");
   }
