#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#include <bits/stdc++.h>
using pii = std::pair<int, int>;
const int NMAX = (int)1e9;
const int SNMAX = (int)sqrt(NMAX) + 1;
std::bitset<NMAX + 1> bits;
int main() {
bits[0] = bits[1] = 1;
std::vector<pii> smallPrimes;
for (int i = 2; i <= SNMAX; ++i) {
if (!bits[i]) {
smallPrimes.push_back({i, i * i});
for (int j = i * i; j <= SNMAX; j += i) {
bits[j] = 1;
}
}
}
const int blockSize = 1 << 18;
for (int from = 0; from <= NMAX; from += blockSize) {
int to = std::min(from + blockSize - 1, NMAX);
for (pii& p : smallPrimes) {
for (; p.second <= to; p.second += p.first) bits[p.second] = 1;
}
}
bits.flip();
//iterate over primes
int64_t sum(0);
int cnt(0);
for (int p = bits._Find_first(); p < bits.size(); p = bits._Find_next(p)) {
sum += p;
cnt++;
}
assert(bits.count() == cnt);
std::cout << "sum = " << sum << std::endl;
std::cout << "cnt = " << cnt << std::endl;
return 0;
}
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKI3ByYWdtYSBHQ0MgdGFyZ2V0KCJhdngiKQojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgcGlpID0gc3RkOjpwYWlyPGludCwgaW50PjsKY29uc3QgaW50IE5NQVggPSAoaW50KTFlOTsKY29uc3QgaW50IFNOTUFYID0gKGludClzcXJ0KE5NQVgpICsgMTsKc3RkOjpiaXRzZXQ8Tk1BWCArIDE+IGJpdHM7CmludCBtYWluKCkgewoJYml0c1swXSA9IGJpdHNbMV0gPSAxOwoJc3RkOjp2ZWN0b3I8cGlpPiBzbWFsbFByaW1lczsKCWZvciAoaW50IGkgPSAyOyBpIDw9IFNOTUFYOyArK2kpIHsKCQlpZiAoIWJpdHNbaV0pIHsKCQkJc21hbGxQcmltZXMucHVzaF9iYWNrKHtpLCBpICogaX0pOwoJCQlmb3IgKGludCBqID0gaSAqIGk7IGogPD0gU05NQVg7IGogKz0gaSkgewoJCQkJYml0c1tqXSA9IDE7CgkJCX0KCQl9Cgl9Cgljb25zdCBpbnQgYmxvY2tTaXplID0gMSA8PCAxODsKCWZvciAoaW50IGZyb20gPSAwOyBmcm9tIDw9IE5NQVg7IGZyb20gKz0gYmxvY2tTaXplKSB7CgkJaW50IHRvID0gc3RkOjptaW4oZnJvbSArIGJsb2NrU2l6ZSAtIDEsIE5NQVgpOwoJCWZvciAocGlpJiBwIDogc21hbGxQcmltZXMpIHsKCQkJZm9yICg7IHAuc2Vjb25kIDw9IHRvOyBwLnNlY29uZCArPSBwLmZpcnN0KSBiaXRzW3Auc2Vjb25kXSA9IDE7CgkJfQoJfQoJYml0cy5mbGlwKCk7CgkvL2l0ZXJhdGUgb3ZlciBwcmltZXMKCWludDY0X3Qgc3VtKDApOwoJaW50IGNudCgwKTsKCWZvciAoaW50IHAgPSBiaXRzLl9GaW5kX2ZpcnN0KCk7IHAgPCBiaXRzLnNpemUoKTsgcCA9IGJpdHMuX0ZpbmRfbmV4dChwKSkgewoJCXN1bSArPSBwOwoJCWNudCsrOwoJfQogICAgYXNzZXJ0KGJpdHMuY291bnQoKSA9PSBjbnQpOwoJc3RkOjpjb3V0IDw8ICJzdW0gPSAiIDw8IHN1bSA8PCBzdGQ6OmVuZGw7CglzdGQ6OmNvdXQgPDwgImNudCA9ICIgPDwgY250IDw8IHN0ZDo6ZW5kbDsKCXJldHVybiAwOwp9