#include <iostream>
#include <utility>

template <class T>
class Sieve {
  int buffsize;
  T *buff;
  static std::pair<int, int> index(int n) {
    std::pair<int, int> retv;
    retv.first = (n - 1) / (8 * sizeof(T)); /* zero origin */
    int bit = (n - 1) % (8 * sizeof(T));    /* zero origin */
    T mask = 1;
    for (int i = 0; i < bit; i++) mask = (mask << 1);
    retv.second = mask;
    return retv;
  }
  
public:
  Sieve(int n) {
    std::pair<int, int> retindexf = index(n);
    buffsize = retindexf.first + 1; /* zero origin */
    buff = new T [buffsize];
    for (int i = 0; i < buffsize; i++) buff[i] = 0;
  }
  ~Sieve() {
    delete buff;
  }
  void setSieve(int n) {
    std::pair<int, int> maskpos = index(n);
    buff[maskpos.first] = buff[maskpos.first] | maskpos.second;
  }
  bool isSieveTrue(int n) {
    std::pair<int, int> maskpos = index(n);    
    return buff[maskpos.first] & maskpos.second;
  }
};

template <class T>
class SieveDerived : private Sieve<T> {
  static int index(int n) {
    int r1 = n / 30;
    int r2 = n % 30;
    switch (r2) {
    case 0:
      /* 1 */
    case 2:
    case 3:
    case 4:
    case 5:
    case 6:
      /* 7 */
    case 8:
    case 9:
    case 10:
      /* 11 */
    case 12:
      /* 13 */
    case 14:
    case 15:
    case 16:
      /* 17 */
    case 18:
      /* 19 */
    case 20:
    case 21:
    case 22:
      /* 23 */
    case 24:
    case 25:
    case 26:
    case 27:
    case 28:
      /* 29 */
      return 0;

    case 1:
      return 8 * r1 + 1;
    case 7:
      return 8 * r1 + 2;
    case 11:
      return 8 * r1 + 3;
    case 13:
      return 8 * r1 + 4;
    case 17:
      return 8 * r1 + 5;
    case 19:
      return 8 * r1 + 6;
    case 23:
      return 8 * r1 + 7;
    case 29:
      return 8 * r1 + 8;

    default:
      return 0;
    }
  }
  
public:
//  SieveDerived(int n) : Sieve<T>(({int r; while((r = index(n)) == 0) n--; r;})) { } /* HERE!! */
  SieveDerived(int n) : Sieve<T>([](int n)->int{int r; while ((r = index(n)) == 0) n--; return r;}(n)) { } /* HERE!! */
  ~SieveDerived() { }
  void setSieve(int n) {
    int r = index(n);
    if (r == 0) return;
    return ((Sieve<T> *)this)->setSieve(r);
  }
  bool isSieveTrue(int n) {
    int r = index(n);
    if (r == 0) return true;
    return ((Sieve<T> *)this)->isSieveTrue(index(n));
  }
};

constexpr int MAXNUM = 1000;

int main() {
  SieveDerived<int> sieve(MAXNUM);
  int n = 0;
  sieve.setSieve(1);
  sieve.setSieve(2); std::cout << 2 << ", "; n++;
  sieve.setSieve(3); std::cout << 3 << ", "; n++;
  sieve.setSieve(4);
  sieve.setSieve(5); std::cout << 5 << ", "; n++;
  for (int i = 6; i <= MAXNUM; i++) {
    if (!sieve.isSieveTrue(i)) {
      std::cout << i << ", ";
      n++;
      for (int j = i; j <= MAXNUM; j += i) sieve.setSieve(j);
    }
  }
  std::cout << std::endl << "n = " << n << std::endl;
  return 0;
}
/* end */