第i个数有多少种相加的方法：dp[ i ]=dp[ i ]+dp[ i -素数 ]；
假设有500个素数，时间复杂度500*1000=5e5； 
#include <iostream>

using namespace std;

const int N=1004;
long long  prime[N],dp[N];
bool st[N];
int n,cnt;

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

int main(int argc, char** argv) {
	cin>>n;
	chart();
	dp[0]=1;
	for(int i=0;i<cnt;i++){
		for(int j=prime[i];j<=n;j++){
			dp[j]=dp[j]+dp[j-prime[i]];
		}
	}
	cout<<dp[n]<<endl;
	return 0;
}

一开始是暴力
把1~n素数找到
然后递归遍历素数相加直到sum大于或等于n回溯
时间复杂度：（估计）（500/2）！