康康我的思路

有了这个思路，代码就很好写了

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;

int primes[N],st[N];
int cnt;

void get_primes(int n)  // 线性筛质数
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int t;
int dp[N];


int main(){
    get_primes(100000);  //找到所有质数

    dp[0]=0,dp[1]=0;           //后面就按照上述递推式计算每个dp[n]的值
    for(int i=2;i<=100000;i++){
        bool flag=false;
        for(int j=0;primes[j]<=i&&j<cnt;j++){  //枚举所有小于i的质数
            if (dp[i-primes[j]]==0){
                dp[i]=1;
                flag=true;
                break;
            }
        }
        if (!flag)  dp[i]=0;
    }

    cin>>t;
    while (t--){
        int x;
        scanf("%d",&x);
        if (dp[x]==1)  cout<<1<<endl;
        else cout<<0<<endl;
    }

    return 0;
}