代码

#include <bits/stdc++.h>
using namespace std;

// Options Start

// #define NETWORK_FLOW
// #define SEGMENT_TREE
// #define FILE_IO
// #define MULTI_TESTS

// Options End
#ifdef LOCAL_TEST
bool __mem_begin;
#endif
#define int long long
#define mid ((l + r) >> 1)
#ifndef LOCAL_TEST
#define endl '\n'
#endif
#ifdef SEGMENT_TREE
#define lson (p << 1)
#define rson (p << 1 | 1)
#endif
#ifdef NETWORK_FLOW
#define rev(p) (p ^ 1)
#endif

const int MAXN = 4e6 + 5;
bitset<MAXN> is;
int prm[MAXN], cnt;

void work() {
	for (int i = 1; i < MAXN; ++i) {
		if (!is[i]) prm[++cnt] = i;
		for (int j = 1; j <= cnt && prm[j] * i < MAXN; ++j) {
			is[prm[j] * i] = true;
		}
	}
}

#ifdef LOCAL_TEST
bool __mem_end;
#endif

signed main(void) {
	ios::sync_with_stdio(false); cin.tie(NULL);
	srand(time(nullptr));
#ifdef LOCAL_TEST
	auto __time_begin = clock();
#endif
#ifdef FILE_IO
#ifndef LOCAL_TEST
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
#endif
#ifdef MULTI_TESTS
	int T = 1; cin >> T; T--;
	while (T--) work();
#endif
	work();
#ifdef LOCAL_TEST
	auto __time_end = clock();
	cerr << "Time: " << __time_end - __time_begin << "" << endl;
	cerr << "Memory: " << (&__mem_end - &__mem_begin) / 1024 << "KiB" << endl;
#endif
	return 0;
}

评测结果