砍柴 参考代码

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

typedef long long LL;
const int maxn = 100000 + 100;
int T, n, cnt;
int ans[maxn], prime[maxn];
bool vis[maxn];

void init(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            prime[cnt++] = i;
        }
        for (int j = 0; j < cnt && i <= n / prime[j]; ++j) {
            int k = i * prime[j];
            vis[k] = true;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    init(maxn - 1);
    for (int i = 2; i < maxn; ++i) {
        for (int j = 0; j < cnt && i >= prime[j]; ++j) {
            if (ans[i - prime[j]] == 0) {
                ans[i] = 1;
                break;
            }
        }
    }
    cin >> T;
    while (T--) {
        cin >> n;
        cout << ans[n] << endl;
    }

    return 0;
}