Advertisement
Guest User

get_primes7 - C++ version

a guest
Jul 8th, 2012
276
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement