Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement