#include "stdafx.h"
#include <iostream>   
#include <math.h>   
#include <sys/time.h>   
 
using namespace std;   
 
double generate(int max) {   
  struct timeval start;   
  struct timezone tz;   
  gettimeofday(&start, &tz);   
 
  bool *sieve = new bool[max];   
  for (int i=0; i<max; i++) sieve[i] = true;   
  sieve[0] = false;   
  sieve[1] = false;   
  for (int n=2; n<sqrt(max); n++) {   
    if (sieve[n]) {   
      for (int j=2*n; j<max; j+=n)   
        sieve[j] = false;   
    }   
  }   
 
  struct timeval end;   
  gettimeofday(&end, &tz);   
 
  double startSecond = start.tv_usec/1000000.0;   
  double endSecond = (end.tv_sec - start.tv_sec) + end.tv_usec/1000000.0;   
  return endSecond - startSecond;   
}   
 
int main(int argc, char * argv[])   
{   
  for (int i=100000; i<=5000000; i+=100000) {   
    double time = generate(i);   
    cout << i << " " << time << "\n";   
  }   
}