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

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;
  /* initialize the table. */
  for(i=0; i<n2; i++) tab[i] = 0;
  /* main loop */
  for(i=2; i<n; i++)
    if(tab[i] == 0)
      for(k=i*i; k<n2; k+=i)
	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));
}