/* Sieve of Eratosthenes.  C code by Frank Pilhofer. */

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

#define TEST(f,x)	(*(f+((x)>>4))&(1<<(((x)&15L)>>1)))
#define SET(f,x)	*(f+((x)>>4))|=1<<(((x)&15L)>>1)

void main(int argc, char *argv[])
{
  unsigned char *feld=NULL, *zzz;
  unsigned long teste=1, max, mom, hits=1, count, alloc, s=0, e=1;
  time_t begin;

  if (argc > 1)
    max = atol (argv[1]) + 10000;
  else
    max = 14010000L;

  while (feld==NULL)
        zzz = feld = malloc (alloc=(((max-=10000L)>>4)+1L));

  for (count=0; count<alloc; count++) *zzz++ = 0x00;

  printf ("Searching prime numbers to : %ld\n", max);

  begin = time (NULL);
  while ((teste+=2) < max)
        if (!TEST(feld, teste)) {
                if  (++hits%2000L==0) {printf (" %ld. prime number\x0d", hits); fflush(stdout);}
                for (mom=3L*teste; mom<max; mom+=teste<<1) SET (feld, mom);
                }

  printf (" %ld prime numbers foundn %ld secs.\n\nShow prime numbers", 
          hits, time(NULL)-begin);

  while (s<e) {
        printf ("\n\nStart of Area : "); fflush (stdout); scanf ("%ld", &s);
        printf ("End   of Area : ");     fflush (stdout); scanf ("%ld", &e);

        count=s-2; if (s%2==0) count++;
        while ((count+=2)<e) if (!TEST(feld,count)) printf ("%ld\t", count);
        }
  free (feld);
}