#include "stdafx.h"
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;

typedef std::vector<int> IntVector;

struct gen {
  gen(int startVal, int step): 
    m_currVal(startVal), m_step(step) {}
  
  int operator()() { 
      int res = m_currVal;
      m_currVal += m_step;
      return res;
  }
private:
   int m_currVal;
   int m_step;
};

inline int round(double value) {
  double val1;

  if (value < 0.0)
    val1 = value - 0.5;
  else
    val1 = value + 0.5;

  int intPart = static_cast<int>(val1);
  return intPart;
}

void get_primes7(int n, IntVector &res)
{
  res.clear();
  if (n < 2)
    return;

  if (n == 2)
  {
    res.push_back(2);
    return;
  }

  int cnt = (n - 3 + 2)/2;
  IntVector s(cnt);

  generate_n(s.begin(), cnt, gen(3,2));

  int mroot = round(sqrt(static_cast<double>(n)));
  int half = s.size();
  int i = 0;
  int m = 3;
  int j;

  while (m <= mroot) 
  {
    if (s[i]) {
      j = (m * m - 3) / 2; 
      s[j] = 0;
      while (j < half)
      {
        s[j] = 0;
        j += m;
      }
    }

    i++;
    m = 2 * i + 3;
  }

  res.push_back(2);
  for(IntVector::iterator it = s.begin(), epos = s.end(); it != epos; ++it)
  {
    if (*it)
      res.push_back(*it);
  }

  //return
}

int main(int argc, char* argv[])
{
  IntVector res;

  for(int i = 1; i <= 50; i++)
  {
    get_primes7(1000000, res);
    cout << "Found " << res.size() << " prime numbers." << endl;
  }
  
  return 0;
}