#include <bits/stdc++.h>
using namespace std;
 
const int NMAX = (int)1e9;
int main() {
    bitset<NMAX / 2> bits;
    bits.set();
	auto sum = 2LL;
	int cnt = 1;
    for (int i = 3; i / 2 < bits.size(); i = 2 * bits._Find_next(i / 2) + 1) {
        sum += i;
        ++cnt;
        for (auto j = (int64_t) i * i / 2; j < bits.size(); j += i) 
            bits[j] = 0;
    }
    for(int i = 0 ; i <= 10 ;i++) cout << bits[i] << " " <<i << endl;
	cout << "sum = " << sum << endl;
	cout << "cnt = " << cnt << endl;
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTk1BWCA9IChpbnQpMWU5OwppbnQgbWFpbigpIHsKICAgIGJpdHNldDxOTUFYIC8gMj4gYml0czsKICAgIGJpdHMuc2V0KCk7CglhdXRvIHN1bSA9IDJMTDsKCWludCBjbnQgPSAxOwogICAgZm9yIChpbnQgaSA9IDM7IGkgLyAyIDwgYml0cy5zaXplKCk7IGkgPSAyICogYml0cy5fRmluZF9uZXh0KGkgLyAyKSArIDEpIHsKICAgICAgICBzdW0gKz0gaTsKICAgICAgICArK2NudDsKICAgICAgICBmb3IgKGF1dG8gaiA9IChpbnQ2NF90KSBpICogaSAvIDI7IGogPCBiaXRzLnNpemUoKTsgaiArPSBpKSAKICAgICAgICAgICAgYml0c1tqXSA9IDA7CiAgICB9CiAgICBmb3IoaW50IGkgPSAwIDsgaSA8PSAxMCA7aSsrKSBjb3V0IDw8IGJpdHNbaV0gPDwgIiAiIDw8aSA8PCBlbmRsOwoJY291dCA8PCAic3VtID0gIiA8PCBzdW0gPDwgZW5kbDsKCWNvdXQgPDwgImNudCA9ICIgPDwgY250IDw8IGVuZGw7CglyZXR1cm4gMDsKfQ==