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

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

double
elapsed_time(struct timeval tp[2])
{
  return tp[1].tv_sec-tp[0].tv_sec+1e-6*(tp[1].tv_usec-tp[0].tv_usec);
}

void
print_prims(int n, char *tab){
  int n2=n*n, i;
  for(i=2; i<n2; i++)
    if(tab[i] == 0)
      printf(" %d", i);
  putchar('\n');
}

void
sieve (int n, char *tab){
  int n2=n*n,i,j,k,i2,k0,k1;
  /* initialize the table. */
  for(i=0; i<n2; i++) tab[i] = 0;
  /* main loop {i=2,i2=4}=>{i=4,i2=16}=>{i=16,i2=256}=>... */
  for(i=2,i2=MIN(4,n); i<n; i=i2,i2=MIN(i*i,n))
    /* sieve (write) tab[i*i .. (n2-1)] by reading tab[i .. (i*i-1)]. */
    for(k0=i*i,k1=MIN(k0+BSIZE,n2); k0<n2; k0=k1,k1=MIN(k0+BSIZE,n2))
      for(j=i; j<i2; j++)
	if(tab[j] == 0)
	  if(j*j>k1)
	    break;
	  else
	    for(k=MAX(j*j,k0),k+=j-1,k-=k%j; k<k1; k+=j)
	      tab[k] = 1;
}

main(int argc, char *argv[])
{
  char *tab;
  struct timeval tp[2];
  int n = 10, d = 0;
  if(argc > 1) n = atol(argv[1]);
  if(argc > 2) d = 1;
  tab = (char *) malloc(sizeof(char)*n*n);
  gettimeofday(tp, 0);
  sieve(n, tab);
  gettimeofday(tp+1, 0);
  if(d) print_prims(n, tab);
  printf("%lf\n", elapsed_time(tp));
}