fork(2) download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC target("avx")
  3.  
  4. #include <stdio.h>
  5.  
  6. #define LIMIT 1000000000
  7. #define SEGMENT_SIZE (16*1024)
  8.  
  9. int pr[51000000], pc = 0;
  10. const int p_off[8] = { 1, 7, 11, 13, 17, 19, 23, 29 };
  11. const int pd[8] = { 6, 4, 2, 4, 2, 4, 6, 2 };
  12. const char p_int[8][8] =
  13. {
  14.   { 0, 0, 0, 0, 0, 0, 0, 0 },
  15.   { 0, 1, 2, 3, 3, 4, 5, 6 },
  16.   { 0, 2, 4, 4, 6, 6, 8, 10 },
  17.   { 0, 3, 4, 5, 7, 8, 9, 12 },
  18.   { 0, 3, 6, 7, 9, 10, 13, 16 },
  19.   { 0, 4, 6, 8, 10, 12, 14, 18 },
  20.   { 0, 5, 8, 9, 13, 14, 17, 22 },
  21.   { 0, 6, 10, 12, 16, 18, 22, 28 }
  22. };
  23. const char p_rest[8][8] =
  24. {
  25.   { 0, 1, 2, 3, 4, 5, 6, 7 },
  26.   { 1, 5, 4, 0, 7, 3, 2, 6 },
  27.   { 2, 4, 0, 6, 1, 7, 3, 5 },
  28.   { 3, 0, 6, 5, 2, 1, 7, 4 },
  29.   { 4, 7, 1, 2, 5, 6, 0, 3 },
  30.   { 5, 3, 7, 1, 6, 0, 4, 2 },
  31.   { 6, 2, 3, 7, 0, 4, 5, 1 },
  32.   { 7, 6, 5, 4, 3, 2, 1, 0 }
  33. };
  34.  
  35. #define SHAS(_n) (p_seg[(_n)>>4] & (1u << (((_n)>>1) & 0x7)))
  36. #define SSET(_n) (p_seg[(_n)>>4] |= (1u << (((_n)>>1) & 0x7)))
  37. unsigned char p_seg[SEGMENT_SIZE], p_diff[3500];
  38. int p_next[3500], spc;
  39.  
  40. void gen( void )
  41. {
  42.   int i, j, id, jd, last = 0;
  43.  
  44.   spc = 0;
  45.   for( i = 7, id = 1; i <= 31622; i += pd[id++ & 7])
  46.     if( !SHAS(i) )
  47.     {
  48.       int off = id & 7, bl = id >> 3;
  49.       p_diff[spc] = (unsigned char) (((id >> 3) - (last >> 3)) << 4) | (id & 7);
  50.       p_next[spc] = ((30 * bl * bl + 2 * bl * p_off[off] + p_int[off][off]) << 3) + p_rest[off][off];
  51.       ++spc;
  52.       last = id;
  53.       if( i <= 177 )
  54.       {
  55.         int limit = 31622 / i;
  56.         for( j = i, jd = id; j <= limit; j += pd[jd++ & 7])
  57.         {
  58.           int num = j * i;
  59.           SSET( num );
  60.         }
  61.       }
  62.     }
  63. }
  64.  
  65. #define CHECK(_f,_off) \
  66.     if( !(bi & (_f)) ) \
  67.     { \
  68.       int x = offset + (_off); \
  69.       if( x >= LIMIT ){ offset += 30; break; } \
  70.       prime( x ); \
  71.     }
  72.  
  73. #define MARK0(_f,_d) \
  74.     p_seg[cur] |= 1u << (_f); \
  75.     cur += (_d)
  76.  
  77. #define MARK(_m,_d) \
  78.     if( cur >= SEGMENT_SIZE ){ p_next[p] = (_m); break; } \
  79.     MARK0( _m, _d)
  80.  
  81. #define STEP8(_m1,_d1,_m2,_d2,_m3,_d3,_m4,_d4,_m5,_d5,_m6,_d6,_m7,_d7,_m8,_d8,_n) \
  82.     switch( p_next[p] & 7 ) \
  83.     do \
  84.     { \
  85.       case _m1: MARK( _m1, _d1); \
  86.       case _m2: MARK( _m2, _d2); \
  87.       case _m3: MARK( _m3, _d3); \
  88.       case _m4: MARK( _m4, _d4); \
  89.       case _m5: MARK( _m5, _d5); \
  90.       case _m6: MARK( _m6, _d6); \
  91.       case _m7: MARK( _m7, _d7); \
  92.       case _m8: MARK( _m8, _d8); \
  93.       limit = finish - (_n); \
  94.       while( cur < limit ) \
  95.       { \
  96.         MARK0( _m1, _d1); \
  97.         MARK0( _m2, _d2); \
  98.         MARK0( _m3, _d3); \
  99.         MARK0( _m4, _d4); \
  100.         MARK0( _m5, _d5); \
  101.         MARK0( _m6, _d6); \
  102.         MARK0( _m7, _d7); \
  103.         MARK0( _m8, _d8); \
  104.       } \
  105.     } while (1); \
  106.     break
  107.  
  108. long long sum = 0;
  109.  
  110. /* #define prime(x) pr[pc++] = (x)  */
  111. #define prime(x) pc++, sum += (x)
  112.  
  113. void sieve( void )
  114. {
  115.   int register p, pbl, cur, d2, d4, d6;
  116.   int limit, finish, offset = 0;
  117.  
  118.   pc = 0;
  119.   prime(2);
  120.   prime(3);
  121.   prime(5);
  122.  
  123.   gen();
  124.   for( cur = SEGMENT_SIZE; cur > 0; ) p_seg[--cur] = 0;
  125.   p_seg[0] = 1;
  126.  
  127.   while( offset <= LIMIT )
  128.   {  
  129.     pbl = p_diff[0] >> 3; /* 0; for speedup */
  130.     for( p = 0; p < spc; p++)
  131.     {
  132.       pbl += p_diff[p] >> 3;
  133.       cur = p_next[p] >> 3;
  134.       if( cur >= SEGMENT_SIZE ){ p_next[p] -= SEGMENT_SIZE << 3; continue; }
  135.       finish = SEGMENT_SIZE - 30 * (pbl >> 1);
  136.       d2 = pbl, d4 = d2 + d2, d6 = d4 + d2;
  137.       switch( p_diff[p] & 7 )
  138.       {
  139.          case 0:
  140.            STEP8( 0, d6, 1, d4, 2, d2, 3, d4, 4, d2, 5, d4, 6, d6, 7, d2+1, 1);
  141.          case 1: d2 += 1, d4 += 1, d6 += 1;
  142.            STEP8( 5, d4, 4, d2, 0, d4-1, 7, d2, 3, d4, 2, d6, 6, d2, 1, d6, 7);
  143.          case 2: d4 += 2, d6 += 2;
  144.            STEP8( 0, d2, 6, d4, 1, d2, 7, d4, 3, d6, 5, d2+1, 2, d6, 4, d4, 11);
  145.          case 3: d2 += 1, d4 += 1, d6 += 3;
  146.            STEP8( 5, d4+1, 2, d2, 1, d4, 7, d6, 4, d2, 3, d6, 0, d4, 6, d2, 13);
  147.          case 4: d2 += 1, d4 += 3, d6 += 3;
  148.            STEP8( 5, d2, 6, d4, 0, d6, 3, d2, 4, d6, 7, d4, 1, d2, 2, d4-1, 17);
  149.          case 5: d2 += 2, d4 += 2, d6 += 4;
  150.            STEP8( 0, d4, 4, d6, 2, d2-1, 5, d6, 3, d4, 7, d2, 1, d4, 6, d2, 19);
  151.          case 6: d2 += 1, d4 += 3, d6 += 5;
  152.            STEP8( 5, d6, 1, d2, 6, d6, 2, d4, 3, d2, 7, d4+1, 0, d2, 4, d4, 23);
  153.          case 7: d2 += 2, d4 += 4, d6 += 6;
  154.            STEP8( 0, d2-1, 7, d6, 6, d4, 5, d2, 4, d4, 3, d2, 2, d4, 1, d6, 29);
  155.       }
  156.       cur -= SEGMENT_SIZE;
  157.       p_next[p] |= cur << 3;
  158.     }
  159.     for( cur = 0; cur < SEGMENT_SIZE; cur++)
  160.     {
  161.       register unsigned char bi = p_seg[cur];
  162.       CHECK( 0x01, 1); CHECK( 0x02, 7); CHECK( 0x04, 11); CHECK( 0x08, 13);
  163.       CHECK( 0x10, 17); CHECK( 0x20, 19); CHECK( 0x40, 23); CHECK( 0x80, 29);
  164.       offset += 30;
  165.       p_seg[cur] = 0;
  166.     }
  167.   }
  168. }
  169.  
  170. int main( void )
  171. {
  172.   sieve();
  173.   printf( "sum = %lld\ncnt = %d\n", sum, pc);
  174.   return 0;
  175. }
Success #stdin #stdout 0.82s 4248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
sum = 24739512092254535
cnt = 50847534
https://ideone.com/hzBXbG
language:
C99 (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!