#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#include <stdio.h>
#define LIMIT 1000000000
#define SEGMENT_SIZE (16*1024)
int pr[51000000], pc = 0;
const int p_off[8] = { 1, 7, 11, 13, 17, 19, 23, 29 };
const int pd[8] = { 6, 4, 2, 4, 2, 4, 6, 2 };
const char p_int[8][8] =
{
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 2, 3, 3, 4, 5, 6 },
{ 0, 2, 4, 4, 6, 6, 8, 10 },
{ 0, 3, 4, 5, 7, 8, 9, 12 },
{ 0, 3, 6, 7, 9, 10, 13, 16 },
{ 0, 4, 6, 8, 10, 12, 14, 18 },
{ 0, 5, 8, 9, 13, 14, 17, 22 },
{ 0, 6, 10, 12, 16, 18, 22, 28 }
};
const char p_rest[8][8] =
{
{ 0, 1, 2, 3, 4, 5, 6, 7 },
{ 1, 5, 4, 0, 7, 3, 2, 6 },
{ 2, 4, 0, 6, 1, 7, 3, 5 },
{ 3, 0, 6, 5, 2, 1, 7, 4 },
{ 4, 7, 1, 2, 5, 6, 0, 3 },
{ 5, 3, 7, 1, 6, 0, 4, 2 },
{ 6, 2, 3, 7, 0, 4, 5, 1 },
{ 7, 6, 5, 4, 3, 2, 1, 0 }
};
#define SHAS(_n) (p_seg[(_n)>>4] & (1u << (((_n)>>1) & 0x7)))
#define SSET(_n) (p_seg[(_n)>>4] |= (1u << (((_n)>>1) & 0x7)))
unsigned char p_seg[SEGMENT_SIZE], p_diff[3500];
int p_next[3500], spc;
void gen( void )
{
int i, j, id, jd, last = 0;
spc = 0;
for( i = 7, id = 1; i <= 31622; i += pd[id++ & 7])
if( !SHAS(i) )
{
int off = id & 7, bl = id >> 3;
p_diff[spc] = (unsigned char) (((id >> 3) - (last >> 3)) << 4) | (id & 7);
p_next[spc] = ((30 * bl * bl + 2 * bl * p_off[off] + p_int[off][off]) << 3) + p_rest[off][off];
++spc;
last = id;
if( i <= 177 )
{
int limit = 31622 / i;
for( j = i, jd = id; j <= limit; j += pd[jd++ & 7])
{
int num = j * i;
SSET( num );
}
}
}
}
#define CHECK(_f,_off) \
if( !(bi & (_f)) ) \
{ \
int x = offset + (_off); \
if( x >= LIMIT ){ offset += 30; break; } \
prime( x ); \
}
#define MARK0(_f,_d) \
p_seg[cur] |= 1u << (_f); \
cur += (_d)
#define MARK(_m,_d) \
if( cur >= SEGMENT_SIZE ){ p_next[p] = (_m); break; } \
MARK0( _m, _d)
#define STEP8(_m1,_d1,_m2,_d2,_m3,_d3,_m4,_d4,_m5,_d5,_m6,_d6,_m7,_d7,_m8,_d8,_n) \
switch( p_next[p] & 7 ) \
do \
{ \
case _m1: MARK( _m1, _d1); \
case _m2: MARK( _m2, _d2); \
case _m3: MARK( _m3, _d3); \
case _m4: MARK( _m4, _d4); \
case _m5: MARK( _m5, _d5); \
case _m6: MARK( _m6, _d6); \
case _m7: MARK( _m7, _d7); \
case _m8: MARK( _m8, _d8); \
limit = finish - (_n); \
while( cur < limit ) \
{ \
MARK0( _m1, _d1); \
MARK0( _m2, _d2); \
MARK0( _m3, _d3); \
MARK0( _m4, _d4); \
MARK0( _m5, _d5); \
MARK0( _m6, _d6); \
MARK0( _m7, _d7); \
MARK0( _m8, _d8); \
} \
} while (1); \
break
long long sum = 0;
/* #define prime(x) pr[pc++] = (x) */
#define prime(x) pc++, sum += (x)
void sieve( void )
{
int register p, pbl, cur, d2, d4, d6;
int limit, finish, offset = 0;
pc = 0;
prime(2);
prime(3);
prime(5);
gen();
for( cur = SEGMENT_SIZE; cur > 0; ) p_seg[--cur] = 0;
p_seg[0] = 1;
while( offset <= LIMIT )
{
pbl = p_diff[0] >> 3; /* 0; for speedup */
for( p = 0; p < spc; p++)
{
pbl += p_diff[p] >> 3;
cur = p_next[p] >> 3;
if( cur >= SEGMENT_SIZE ){ p_next[p] -= SEGMENT_SIZE << 3; continue; }
finish = SEGMENT_SIZE - 30 * (pbl >> 1);
d2 = pbl, d4 = d2 + d2, d6 = d4 + d2;
switch( p_diff[p] & 7 )
{
case 0:
STEP8( 0, d6, 1, d4, 2, d2, 3, d4, 4, d2, 5, d4, 6, d6, 7, d2+1, 1);
case 1: d2 += 1, d4 += 1, d6 += 1;
STEP8( 5, d4, 4, d2, 0, d4-1, 7, d2, 3, d4, 2, d6, 6, d2, 1, d6, 7);
case 2: d4 += 2, d6 += 2;
STEP8( 0, d2, 6, d4, 1, d2, 7, d4, 3, d6, 5, d2+1, 2, d6, 4, d4, 11);
case 3: d2 += 1, d4 += 1, d6 += 3;
STEP8( 5, d4+1, 2, d2, 1, d4, 7, d6, 4, d2, 3, d6, 0, d4, 6, d2, 13);
case 4: d2 += 1, d4 += 3, d6 += 3;
STEP8( 5, d2, 6, d4, 0, d6, 3, d2, 4, d6, 7, d4, 1, d2, 2, d4-1, 17);
case 5: d2 += 2, d4 += 2, d6 += 4;
STEP8( 0, d4, 4, d6, 2, d2-1, 5, d6, 3, d4, 7, d2, 1, d4, 6, d2, 19);
case 6: d2 += 1, d4 += 3, d6 += 5;
STEP8( 5, d6, 1, d2, 6, d6, 2, d4, 3, d2, 7, d4+1, 0, d2, 4, d4, 23);
case 7: d2 += 2, d4 += 4, d6 += 6;
STEP8( 0, d2-1, 7, d6, 6, d4, 5, d2, 4, d4, 3, d2, 2, d4, 1, d6, 29);
}
cur -= SEGMENT_SIZE;
p_next[p] |= cur << 3;
}
for( cur = 0; cur < SEGMENT_SIZE; cur++)
{
register unsigned char bi = p_seg[cur];
CHECK( 0x01, 1); CHECK( 0x02, 7); CHECK( 0x04, 11); CHECK( 0x08, 13);
CHECK( 0x10, 17); CHECK( 0x20, 19); CHECK( 0x40, 23); CHECK( 0x80, 29);
offset += 30;
p_seg[cur] = 0;
}
}
}
int main( void )
{
sieve();
printf( "sum = %lld\ncnt = %d\n", sum
, pc
); return 0;
}
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKI3ByYWdtYSBHQ0MgdGFyZ2V0KCJhdngiKQoKI2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIExJTUlUIDEwMDAwMDAwMDAKI2RlZmluZSBTRUdNRU5UX1NJWkUgKDE2KjEwMjQpCgppbnQgcHJbNTEwMDAwMDBdLCBwYyA9IDA7CmNvbnN0IGludCBwX29mZls4XSA9IHsgMSwgNywgMTEsIDEzLCAxNywgMTksIDIzLCAyOSB9Owpjb25zdCBpbnQgcGRbOF0gPSB7IDYsIDQsIDIsIDQsIDIsIDQsIDYsIDIgfTsKY29uc3QgY2hhciBwX2ludFs4XVs4XSA9CnsKICB7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAgfSwKICB7IDAsIDEsIDIsIDMsIDMsIDQsIDUsIDYgfSwKICB7IDAsIDIsIDQsIDQsIDYsIDYsIDgsIDEwIH0sCiAgeyAwLCAzLCA0LCA1LCA3LCA4LCA5LCAxMiB9LAogIHsgMCwgMywgNiwgNywgOSwgMTAsIDEzLCAxNiB9LAogIHsgMCwgNCwgNiwgOCwgMTAsIDEyLCAxNCwgMTggfSwKICB7IDAsIDUsIDgsIDksIDEzLCAxNCwgMTcsIDIyIH0sCiAgeyAwLCA2LCAxMCwgMTIsIDE2LCAxOCwgMjIsIDI4IH0KfTsKY29uc3QgY2hhciBwX3Jlc3RbOF1bOF0gPQp7CiAgeyAwLCAxLCAyLCAzLCA0LCA1LCA2LCA3IH0sCiAgeyAxLCA1LCA0LCAwLCA3LCAzLCAyLCA2IH0sCiAgeyAyLCA0LCAwLCA2LCAxLCA3LCAzLCA1IH0sCiAgeyAzLCAwLCA2LCA1LCAyLCAxLCA3LCA0IH0sCiAgeyA0LCA3LCAxLCAyLCA1LCA2LCAwLCAzIH0sCiAgeyA1LCAzLCA3LCAxLCA2LCAwLCA0LCAyIH0sCiAgeyA2LCAyLCAzLCA3LCAwLCA0LCA1LCAxIH0sCiAgeyA3LCA2LCA1LCA0LCAzLCAyLCAxLCAwIH0KfTsKCiNkZWZpbmUgU0hBUyhfbikgKHBfc2VnWyhfbik+PjRdICYgKDF1IDw8ICgoKF9uKT4+MSkgJiAweDcpKSkKI2RlZmluZSBTU0VUKF9uKSAocF9zZWdbKF9uKT4+NF0gfD0gKDF1IDw8ICgoKF9uKT4+MSkgJiAweDcpKSkKdW5zaWduZWQgY2hhciBwX3NlZ1tTRUdNRU5UX1NJWkVdLCBwX2RpZmZbMzUwMF07CmludCBwX25leHRbMzUwMF0sIHNwYzsKCnZvaWQgZ2VuKCB2b2lkICkKewogIGludCBpLCBqLCBpZCwgamQsIGxhc3QgPSAwOwoKICBzcGMgPSAwOwogIGZvciggaSA9IDcsIGlkID0gMTsgaSA8PSAzMTYyMjsgaSArPSBwZFtpZCsrICYgN10pCiAgICBpZiggIVNIQVMoaSkgKQogICAgewogICAgICBpbnQgb2ZmID0gaWQgJiA3LCBibCA9IGlkID4+IDM7CiAgICAgIHBfZGlmZltzcGNdID0gKHVuc2lnbmVkIGNoYXIpICgoKGlkID4+IDMpIC0gKGxhc3QgPj4gMykpIDw8IDQpIHwgKGlkICYgNyk7CiAgICAgIHBfbmV4dFtzcGNdID0gKCgzMCAqIGJsICogYmwgKyAyICogYmwgKiBwX29mZltvZmZdICsgcF9pbnRbb2ZmXVtvZmZdKSA8PCAzKSArIHBfcmVzdFtvZmZdW29mZl07CiAgICAgICsrc3BjOwogICAgICBsYXN0ID0gaWQ7CiAgICAgIGlmKCBpIDw9IDE3NyApCiAgICAgIHsKICAgICAgICBpbnQgbGltaXQgPSAzMTYyMiAvIGk7CiAgICAgICAgZm9yKCBqID0gaSwgamQgPSBpZDsgaiA8PSBsaW1pdDsgaiArPSBwZFtqZCsrICYgN10pCiAgICAgICAgewogICAgICAgICAgaW50IG51bSA9IGogKiBpOwogICAgICAgICAgU1NFVCggbnVtICk7CiAgICAgICAgfQogICAgICB9CiAgICB9Cn0KCiNkZWZpbmUgQ0hFQ0soX2YsX29mZikgXAogICAgaWYoICEoYmkgJiAoX2YpKSApIFwKICAgIHsgXAogICAgICBpbnQgeCA9IG9mZnNldCArIChfb2ZmKTsgXAogICAgICBpZiggeCA+PSBMSU1JVCApeyBvZmZzZXQgKz0gMzA7IGJyZWFrOyB9IFwKICAgICAgcHJpbWUoIHggKTsgXAogICAgfQoKI2RlZmluZSBNQVJLMChfZixfZCkgXAogICAgcF9zZWdbY3VyXSB8PSAxdSA8PCAoX2YpOyBcCiAgICBjdXIgKz0gKF9kKQoKI2RlZmluZSBNQVJLKF9tLF9kKSBcCiAgICBpZiggY3VyID49IFNFR01FTlRfU0laRSApeyBwX25leHRbcF0gPSAoX20pOyBicmVhazsgfSBcCiAgICBNQVJLMCggX20sIF9kKQoKI2RlZmluZSBTVEVQOChfbTEsX2QxLF9tMixfZDIsX20zLF9kMyxfbTQsX2Q0LF9tNSxfZDUsX202LF9kNixfbTcsX2Q3LF9tOCxfZDgsX24pIFwKICAgIHN3aXRjaCggcF9uZXh0W3BdICYgNyApIFwKICAgIGRvIFwKICAgIHsgXAogICAgICBjYXNlIF9tMTogTUFSSyggX20xLCBfZDEpOyBcCiAgICAgIGNhc2UgX20yOiBNQVJLKCBfbTIsIF9kMik7IFwKICAgICAgY2FzZSBfbTM6IE1BUksoIF9tMywgX2QzKTsgXAogICAgICBjYXNlIF9tNDogTUFSSyggX200LCBfZDQpOyBcCiAgICAgIGNhc2UgX201OiBNQVJLKCBfbTUsIF9kNSk7IFwKICAgICAgY2FzZSBfbTY6IE1BUksoIF9tNiwgX2Q2KTsgXAogICAgICBjYXNlIF9tNzogTUFSSyggX203LCBfZDcpOyBcCiAgICAgIGNhc2UgX204OiBNQVJLKCBfbTgsIF9kOCk7IFwKICAgICAgbGltaXQgPSBmaW5pc2ggLSAoX24pOyBcCiAgICAgIHdoaWxlKCBjdXIgPCBsaW1pdCApIFwKICAgICAgeyBcCiAgICAgICAgTUFSSzAoIF9tMSwgX2QxKTsgXAogICAgICAgIE1BUkswKCBfbTIsIF9kMik7IFwKICAgICAgICBNQVJLMCggX20zLCBfZDMpOyBcCiAgICAgICAgTUFSSzAoIF9tNCwgX2Q0KTsgXAogICAgICAgIE1BUkswKCBfbTUsIF9kNSk7IFwKICAgICAgICBNQVJLMCggX202LCBfZDYpOyBcCiAgICAgICAgTUFSSzAoIF9tNywgX2Q3KTsgXAogICAgICAgIE1BUkswKCBfbTgsIF9kOCk7IFwKICAgICAgfSBcCiAgICB9IHdoaWxlICgxKTsgXAogICAgYnJlYWsKCmxvbmcgbG9uZyBzdW0gPSAwOwoKLyogI2RlZmluZSBwcmltZSh4KSBwcltwYysrXSA9ICh4KSAgKi8KI2RlZmluZSBwcmltZSh4KSBwYysrLCBzdW0gKz0gKHgpCgp2b2lkIHNpZXZlKCB2b2lkICkKewogIGludCByZWdpc3RlciBwLCBwYmwsIGN1ciwgZDIsIGQ0LCBkNjsKICBpbnQgbGltaXQsIGZpbmlzaCwgb2Zmc2V0ID0gMDsKCiAgcGMgPSAwOwogIHByaW1lKDIpOwogIHByaW1lKDMpOwogIHByaW1lKDUpOwoKICBnZW4oKTsKICBmb3IoIGN1ciA9IFNFR01FTlRfU0laRTsgY3VyID4gMDsgKSBwX3NlZ1stLWN1cl0gPSAwOwogIHBfc2VnWzBdID0gMTsKCiAgd2hpbGUoIG9mZnNldCA8PSBMSU1JVCApCiAgeyAgCiAgICBwYmwgPSBwX2RpZmZbMF0gPj4gMzsgLyogMDsgZm9yIHNwZWVkdXAgKi8KICAgIGZvciggcCA9IDA7IHAgPCBzcGM7IHArKykKICAgIHsKICAgICAgcGJsICs9IHBfZGlmZltwXSA+PiAzOwogICAgICBjdXIgPSBwX25leHRbcF0gPj4gMzsKICAgICAgaWYoIGN1ciA+PSBTRUdNRU5UX1NJWkUgKXsgcF9uZXh0W3BdIC09IFNFR01FTlRfU0laRSA8PCAzOyBjb250aW51ZTsgfQogICAgICBmaW5pc2ggPSBTRUdNRU5UX1NJWkUgLSAzMCAqIChwYmwgPj4gMSk7CiAgICAgIGQyID0gcGJsLCBkNCA9IGQyICsgZDIsIGQ2ID0gZDQgKyBkMjsKICAgICAgc3dpdGNoKCBwX2RpZmZbcF0gJiA3ICkKICAgICAgewogICAgICAgICBjYXNlIDA6CiAgICAgICAgICAgU1RFUDgoIDAsIGQ2LCAxLCBkNCwgMiwgZDIsIDMsIGQ0LCA0LCBkMiwgNSwgZDQsIDYsIGQ2LCA3LCBkMisxLCAxKTsKICAgICAgICAgY2FzZSAxOiBkMiArPSAxLCBkNCArPSAxLCBkNiArPSAxOwogICAgICAgICAgIFNURVA4KCA1LCBkNCwgNCwgZDIsIDAsIGQ0LTEsIDcsIGQyLCAzLCBkNCwgMiwgZDYsIDYsIGQyLCAxLCBkNiwgNyk7CiAgICAgICAgIGNhc2UgMjogZDQgKz0gMiwgZDYgKz0gMjsKICAgICAgICAgICBTVEVQOCggMCwgZDIsIDYsIGQ0LCAxLCBkMiwgNywgZDQsIDMsIGQ2LCA1LCBkMisxLCAyLCBkNiwgNCwgZDQsIDExKTsKICAgICAgICAgY2FzZSAzOiBkMiArPSAxLCBkNCArPSAxLCBkNiArPSAzOwogICAgICAgICAgIFNURVA4KCA1LCBkNCsxLCAyLCBkMiwgMSwgZDQsIDcsIGQ2LCA0LCBkMiwgMywgZDYsIDAsIGQ0LCA2LCBkMiwgMTMpOwogICAgICAgICBjYXNlIDQ6IGQyICs9IDEsIGQ0ICs9IDMsIGQ2ICs9IDM7CiAgICAgICAgICAgU1RFUDgoIDUsIGQyLCA2LCBkNCwgMCwgZDYsIDMsIGQyLCA0LCBkNiwgNywgZDQsIDEsIGQyLCAyLCBkNC0xLCAxNyk7CiAgICAgICAgIGNhc2UgNTogZDIgKz0gMiwgZDQgKz0gMiwgZDYgKz0gNDsKICAgICAgICAgICBTVEVQOCggMCwgZDQsIDQsIGQ2LCAyLCBkMi0xLCA1LCBkNiwgMywgZDQsIDcsIGQyLCAxLCBkNCwgNiwgZDIsIDE5KTsKICAgICAgICAgY2FzZSA2OiBkMiArPSAxLCBkNCArPSAzLCBkNiArPSA1OwogICAgICAgICAgIFNURVA4KCA1LCBkNiwgMSwgZDIsIDYsIGQ2LCAyLCBkNCwgMywgZDIsIDcsIGQ0KzEsIDAsIGQyLCA0LCBkNCwgMjMpOwogICAgICAgICBjYXNlIDc6IGQyICs9IDIsIGQ0ICs9IDQsIGQ2ICs9IDY7CiAgICAgICAgICAgU1RFUDgoIDAsIGQyLTEsIDcsIGQ2LCA2LCBkNCwgNSwgZDIsIDQsIGQ0LCAzLCBkMiwgMiwgZDQsIDEsIGQ2LCAyOSk7CiAgICAgIH0KICAgICAgY3VyIC09IFNFR01FTlRfU0laRTsKICAgICAgcF9uZXh0W3BdIHw9IGN1ciA8PCAzOwogICAgfQogICAgZm9yKCBjdXIgPSAwOyBjdXIgPCBTRUdNRU5UX1NJWkU7IGN1cisrKQogICAgewogICAgICByZWdpc3RlciB1bnNpZ25lZCBjaGFyIGJpID0gcF9zZWdbY3VyXTsKICAgICAgQ0hFQ0soIDB4MDEsIDEpOyBDSEVDSyggMHgwMiwgNyk7IENIRUNLKCAweDA0LCAxMSk7IENIRUNLKCAweDA4LCAxMyk7CiAgICAgIENIRUNLKCAweDEwLCAxNyk7IENIRUNLKCAweDIwLCAxOSk7IENIRUNLKCAweDQwLCAyMyk7IENIRUNLKCAweDgwLCAyOSk7CiAgICAgIG9mZnNldCArPSAzMDsKICAgICAgcF9zZWdbY3VyXSA9IDA7CiAgICB9CiAgfQp9CgppbnQgbWFpbiggdm9pZCApCnsKICBzaWV2ZSgpOwogIHByaW50ZiggInN1bSA9ICVsbGRcbmNudCA9ICVkXG4iLCBzdW0sIHBjKTsKICByZXR1cm4gMDsKfQ==