#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>

using namespace std;

typedef unsigned long int num_t;

template <class NUM>
bool isprime (NUM n)
{
  if (n <= 2) return (n == 2);
  if (n%2 == 0) return false;
  for (NUM d=3; d*d <= n; d+=2) {
    if (n%d == 0) return false;
  }
  return true;
}

num_t f(num_t n)
{
  if (n < 10) return n;
  return num_t(n * log(double(n)));
}


int main (int ac, char **av)
{
  set<num_t> p_used;    // primes > fn (~=f(n)) in seq
  set<num_t> p_missed;  // primes <= n not in seq
  set<num_t> p_missed2; // primes > n, <= fn not in seq
  num_t n_lim = 1000;
  num_t fn;

  if (ac > 1) n_lim = strtoul(av[1], NULL, 0);

  num_t x = 2;
  //  cout << 0 << " " << x << " " << p_missed.size() << " "
  //       << p_missed2.size() << " " << p_used.size() << endl;
  p_used.insert(x);
  fn = 1;
  for (num_t n=1; n <= n_lim; ++n) {
    // update p_missed2
    num_t fn2 = f(n);
    while (fn < fn2) {
      if (fn < 3) fn++;
      else fn += 2;
      if (isprime(fn)) {
	set<num_t>::iterator ifn = p_used.find(fn);
	if (ifn == p_used.end()) {
	  p_missed2.insert(fn);
	} else {
	  p_used.erase(ifn);
	}
      }
    }

    // update p_missed
    set<num_t>::iterator in = p_missed2.find(n);
    if (in != p_missed2.end()) {
      p_missed2.erase(in);
      p_missed.insert(n);
    }

    //    cout << "after update, n " << n << " fn " << fn << endl;
    //    cout << "p_missed:";
    //    for (set<num_t>::iterator i = p_missed.begin(); i != p_missed.end(); ++i) {
    //      cout << " " << *i;
    //    }
    //    cout << endl;
    //    cout << "p_missed2:";
    //    for (set<num_t>::iterator i = p_missed2.begin(); i != p_missed2.end(); ++i) {
    //      cout << " " << *i;
    //    }
    //    cout << endl;
    //    cout << "p_used:";
    //    for (set<num_t>::iterator i = p_used.begin(); i != p_used.end(); ++i) {
    //      cout << " " << *i;
    //    }
    //    cout << endl;
    
    x = n - (x % n);
    set<num_t>::iterator ix = p_missed.find(x);
    if (ix != p_missed.end()) {
      cout << n << " " << x << " " << p_missed.size() << " "
	   << p_missed2.size() << " " << p_used.size() << endl;
      p_missed.erase(ix);
      continue;
    }

    x += n;
    while (x <= fn) {
      if ((ix = p_missed2.find(x)) != p_missed2.end()) {
	//	cout << n << " " << x << " " << p_missed.size() << " "
	//	     << p_missed2.size() << " " << p_used.size() << endl;
	p_missed2.erase(ix);
	break;
      }
      x += n;
    }
    
    if (x <= fn) continue;
    while (!isprime (x) || p_used.find(x) != p_used.end()) x += n;
    //    cout << n << " " << x << " " << p_missed.size() << " "
    //	 << p_missed2.size() << " " << p_used.size() << endl;
    p_used.insert(x);
  }
  //  cout << n_lim << " " << x << " " << p_missed.size() << " "
  //       << p_missed2.size() << " " << p_used.size() << endl;

#if 0
  cout << "missed cutoffs (fn " << fn << ")" << endl;
  size_t used = n_lim;
  size_t missed = 0;
  for (num_t p = 3; used > 0; p += 2) {
    if (!isprime(p)) continue;
    if (p <= n_lim) {
      if (p_missed.find(p) != p_missed.end()) {
	missed++;
      } else {
	used--;
      }
    } else if (p <= fn) {
      if (p_missed2.find(p) != p_missed2.end()) {
	missed++;
      } else {
	used--;
      }
    } else {
      if (p_used.find(p) != p_used.end()) {
	used--;
      } else {
	missed++;
      }
    }
    cout << p << " " << used + missed << " " << missed << " " << used << endl;
  }
#endif
}