Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!

# get_primes7 - C++ version

By: a guest on Jul 8th, 2012  |  syntax: C++  |  size: 1.54 KB  |  views: 85  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1.
2. #include "stdafx.h"
3. #include <vector>
4. #include <algorithm>
5. #include <cmath>
6. #include <iostream>
7.
8. using namespace std;
9.
10. typedef std::vector<int> IntVector;
11.
12. struct gen {
13.   gen(int startVal, int step):
14.     m_currVal(startVal), m_step(step) {}
15.
16.   int operator()() {
17.       int res = m_currVal;
18.       m_currVal += m_step;
19.       return res;
20.   }
21. private:
22.    int m_currVal;
23.    int m_step;
24. };
25.
26. inline int round(double value) {
27.   double val1;
28.
29.   if (value < 0.0)
30.     val1 = value - 0.5;
31.   else
32.     val1 = value + 0.5;
33.
34.   int intPart = static_cast<int>(val1);
35.   return intPart;
36. }
37.
38. void get_primes7(int n, IntVector &res)
39. {
40.   res.clear();
41.   if (n < 2)
42.     return;
43.
44.   if (n == 2)
45.   {
46.     res.push_back(2);
47.     return;
48.   }
49.
50.   int cnt = (n - 3 + 2)/2;
51.   IntVector s(cnt);
52.
53.   generate_n(s.begin(), cnt, gen(3,2));
54.
55.   int mroot = round(sqrt(static_cast<double>(n)));
56.   int half = s.size();
57.   int i = 0;
58.   int m = 3;
59.   int j;
60.
61.   while (m <= mroot)
62.   {
63.     if (s[i]) {
64.       j = (m * m - 3) / 2;
65.       s[j] = 0;
66.       while (j < half)
67.       {
68.         s[j] = 0;
69.         j += m;
70.       }
71.     }
72.
73.     i++;
74.     m = 2 * i + 3;
75.   }
76.
77.   res.push_back(2);
78.   for(IntVector::iterator it = s.begin(), epos = s.end(); it != epos; ++it)
79.   {
80.     if (*it)
81.       res.push_back(*it);
82.   }
83.
84.   //return
85. }
86.
87. int main(int argc, char* argv[])
88. {
89.   IntVector res;
90.
91.   for(int i = 1; i <= 50; i++)
92.   {
93.     get_primes7(1000000, res);
94.     cout << "Found " << res.size() << " prime numbers." << endl;
95.   }
96.
97.   return 0;
98. }
clone this paste RAW Paste Data
Top