fork download
copy 
  1. // http://stackoverflow.com/questions/231381/
  2. //    is-this-prime-generator-inefficient-c/235517#235517
  3.  
  4. // by ephemient, answered Oct 24 '08 at 22:45  
  5. // + my edits, 2012-05-16 (1. odds; 2. stages) -- WillNess
  6.  
  7. #include <iostream>
  8. #include <map>
  9.  
  10. using namespace std;
  11.  
  12. template<typename T = int, typename M = map<T, T> >
  13. class odd_prime_iterator {
  14.         public:
  15.             odd_prime_iterator() : current(1), skips() { operator++(); }
  16.             T operator*() { return current; }
  17.             odd_prime_iterator &operator++() {
  18.                 typename M::iterator i;
  19.                 while ((i = skips.find( (current+=2) )) != skips.end()) {
  20.                     T skip = i->second, next = current + skip;
  21.                     skips.erase(i);
  22.                     for (typename M::iterator j = skips.find(next);
  23.                             j != skips.end(); j = skips.find(next += skip)) {}
  24.                     skips[next] = skip;
  25.                 }
  26.                 skips[current * current] = 2 * current;
  27.                 return *this;
  28.             }
  29.         private:
  30.             T current;
  31.             M skips;
  32.     };
  33.  
  34.  
  35. template<typename T = int, typename M = map<T, T> >
  36. class staged_prime_iterator {
  37.         public:
  38.             staged_prime_iterator() : current(1), skips(), base()   // base starts from 3
  39.                 { q = *base * *base; operator++(); }
  40.             T operator*() { return current; }
  41.             staged_prime_iterator &operator++() {
  42.                 while ( 1 )
  43.                 {
  44.                     current += 2;
  45.                     if( current == q )
  46.                     {
  47.                         add_a_skip( current + 2 * *base, 2 * *base);
  48.                         ++base;
  49.                         q = *base * *base;
  50.                         continue;
  51.                     }
  52.                     typename M::iterator i = skips.find( current );
  53.                     if( i == skips.end() )     // not found among the multiples - current is prime
  54.                         break;
  55.  
  56.                     T skip = i->second, next = current + skip;
  57.                     skips.erase(i);
  58.                     add_a_skip( next, skip);
  59.                 }
  60.                 return *this;
  61.             }
  62.             T show_base(){ return *base; }
  63.         private:
  64.             T current, q;
  65.             M skips;
  66.             odd_prime_iterator<T> base;
  67.             void add_a_skip( T next, T skip ) {
  68.                     for (typename M::iterator j = skips.find(next);
  69.                             j != skips.end(); j = skips.find(next += skip)) {}
  70.                     skips[next] = skip;
  71.                     }
  72.     };
  73.  
  74.  
  75. int main() {
  76.         staged_prime_iterator<int> primes;
  77.         // cout << 2 << " ";
  78.         int i = 1;
  79.         for (int k=1; *primes < 10000000-100; ++primes, ++i)  ;
  80.         for (int k=1; *primes < 10000000; ++primes, ++i)  
  81.         {
  82.             if( k++ == 20 ) { cout << endl; k = 1; }
  83.             cout << *primes << " ";
  84.         }
  85.         cout << endl << *primes
  86.              << " {{ " << i << " primes, base = " << primes.show_base() << " }}";
  87.         return 0;
  88. }
  89.  
Success #stdin #stdout 1.71s 2864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9999901 9999907 9999929 9999931 9999937 9999943 9999971 9999973 9999991 
10000019 {{ 664579 primes, base = 3163 }}
https://ideone.com/jXoEL
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!