这道题，其实是一道背包型DP问题 首先，他说要把n分解成质数和，那么我们可以先把n以内的质数都枚举出来，再看能不能加起来等于n。
枚举质数代码：
for(int i=2;i<=sqrt(n);i++) if(!a[i]) for(int j=2;j<=n/i;j++) a[i*j]=1;
把所有的合数标记为1，然后剩下的为0的就是质数啦（当然，1除外）
然后我们可以利用背包来求出最大方案数。
代码如下：
for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){
f[i][j]=f[i-1][j];
if(j>=w[i]) f[i][j]+=f[i][j-w[i]];
}
然后，f[m][n]位置上的数就是答案啦
注意：本蒟蒻发现f[m][n]这个数必须除以2，有点奇怪
printf("%d",f[m][n]/2);
总体来说，AC代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,m=1,w[510];
int a[510];
long long f[510][1010];
int main(){
scanf("%d",&n);
for(int i=2;i<=sqrt(n);i++) if(!a[i]) for(int j=2;j<=n/i;j++) a[i*j]=1;
for(int i=2;i<=n;i++) if(!a[i]) w[m++]=i;
for(int i=1;i<=m;i++) f[i][0]=1;
for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){
f[i][j]=f[i-1][j];
if(j>=w[i]) f[i][j]+=f[i][j-w[i]];
}
printf("%d",f[m][n]/2);
return 0;
}