fork download
copy 
  1. #include <iostream>
  2. #include <utility>
  3.  
  4. template <class T>
  5. class Sieve {
  6.   int buffsize;
  7.   T *buff;
  8.   static std::pair<int, int> index(int n) {
  9.     std::pair<int, int> retv;
  10.     retv.first = (n - 1) / (8 * sizeof(T)); /* zero origin */
  11.     int bit = (n - 1) % (8 * sizeof(T));    /* zero origin */
  12.     T mask = 1;
  13.     for (int i = 0; i < bit; i++) mask = (mask << 1);
  14.     retv.second = mask;
  15.     return retv;
  16.   }
  17.  
  18. public:
  19.   Sieve(int n) {
  20.     std::pair<int, int> retindexf = index(n);
  21.     buffsize = retindexf.first + 1; /* zero origin */
  22.     buff = new T [buffsize];
  23.     for (int i = 0; i < buffsize; i++) buff[i] = 0;
  24.   }
  25.   ~Sieve() {
  26.     delete buff;
  27.   }
  28.   void setSieve(int n) {
  29.     std::pair<int, int> maskpos = index(n);
  30.     buff[maskpos.first] = buff[maskpos.first] | maskpos.second;
  31.   }
  32.   bool isSieveTrue(int n) {
  33.     std::pair<int, int> maskpos = index(n);    
  34.     return buff[maskpos.first] & maskpos.second;
  35.   }
  36. };
  37.  
  38. template <class T>
  39. class SieveDerived : private Sieve<T> {
  40.   static int index(int n) {
  41.     int r1 = n / 30;
  42.     int r2 = n % 30;
  43.     switch (r2) {
  44.     case 0:
  45.       /* 1 */
  46.     case 2:
  47.     case 3:
  48.     case 4:
  49.     case 5:
  50.     case 6:
  51.       /* 7 */
  52.     case 8:
  53.     case 9:
  54.     case 10:
  55.       /* 11 */
  56.     case 12:
  57.       /* 13 */
  58.     case 14:
  59.     case 15:
  60.     case 16:
  61.       /* 17 */
  62.     case 18:
  63.       /* 19 */
  64.     case 20:
  65.     case 21:
  66.     case 22:
  67.       /* 23 */
  68.     case 24:
  69.     case 25:
  70.     case 26:
  71.     case 27:
  72.     case 28:
  73.       /* 29 */
  74.       return 0;
  75.  
  76.     case 1:
  77.       return 8 * r1 + 1;
  78.     case 7:
  79.       return 8 * r1 + 2;
  80.     case 11:
  81.       return 8 * r1 + 3;
  82.     case 13:
  83.       return 8 * r1 + 4;
  84.     case 17:
  85.       return 8 * r1 + 5;
  86.     case 19:
  87.       return 8 * r1 + 6;
  88.     case 23:
  89.       return 8 * r1 + 7;
  90.     case 29:
  91.       return 8 * r1 + 8;
  92.  
  93.     default:
  94.       return 0;
  95.     }
  96.   }
  97.  
  98. public:
  99. //  SieveDerived(int n) : Sieve<T>(({int r; while((r = index(n)) == 0) n--; r;})) { } /* HERE!! */
  100.   SieveDerived(int n) : Sieve<T>([](int n)->int{int r; while ((r = index(n)) == 0) n--; return r;}(n)) { } /* HERE!! */
  101.   ~SieveDerived() { }
  102.   void setSieve(int n) {
  103.     int r = index(n);
  104.     if (r == 0) return;
  105.     return ((Sieve<T> *)this)->setSieve(r);
  106.   }
  107.   bool isSieveTrue(int n) {
  108.     int r = index(n);
  109.     if (r == 0) return true;
  110.     return ((Sieve<T> *)this)->isSieveTrue(index(n));
  111.   }
  112. };
  113.  
  114. constexpr int MAXNUM = 1000;
  115.  
  116. int main() {
  117.   SieveDerived<int> sieve(MAXNUM);
  118.   int n = 0;
  119.   sieve.setSieve(1);
  120.   sieve.setSieve(2); std::cout << 2 << ", "; n++;
  121.   sieve.setSieve(3); std::cout << 3 << ", "; n++;
  122.   sieve.setSieve(4);
  123.   sieve.setSieve(5); std::cout << 5 << ", "; n++;
  124.   for (int i = 6; i <= MAXNUM; i++) {
  125.     if (!sieve.isSieveTrue(i)) {
  126.       std::cout << i << ", ";
  127.       n++;
  128.       for (int j = i; j <= MAXNUM; j += i) sieve.setSieve(j);
  129.     }
  130.   }
  131.   std::cout << std::endl << "n = " << n << std::endl;
  132.   return 0;
  133. }
  134. /* end */
  135.  
Success #stdin #stdout 0s 4328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 
n = 168
https://ideone.com/y3ROXS
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!