#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;
}