显然可以枚举素数转移，然后预处理一下素数即可。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=2e4+10; int n,dp[N],f[N],vis[N]; vector<int> p; void init(int n){ for(int i=2;i<=n;i++) if(!vis[i]){ p.push_back(i); for(int j=i+i;j<=n;j+=i) vis[j]=1; } dp[2]=1,f[2]=1,dp[0]=0; for(int i=3;i<=n;i++){ int ok=0,mi=1e9,mx=-1e9; for(int j:p){ if(j>i) break; if(!dp[i-j]) ok=1,mi=min(mi,f[i-j]); mx=max(mx,f[i-j]); } if(ok) dp[i]=1,f[i]=mi+1; else f[i]=mx+1; } } signed main(){ init(20000); int T; cin>>T; while(T--){ cin>>n; if(dp[n]) cout<<f[n]<<endl; else cout<<-1<<endl; } return 0; }