学步园

分析：

以d[ i ][ j ] 表示数i分解为j个素数的所有方法； 第一个想到的状态转移方程  d[ i ][ j ]  += d[ i -k ][ j-1 ] (k为比i小的素数)，但改状态转移方程并不正确，如d[ 7 ][ 3 ]转移至d[ 5 ] [ 2 ];

5 可分解为 3+2 与刚才的2重复，换句话数d[ i ][ j ] 只依赖  d[ i -k ][ j-1 ] 中由j-1个素数组成并且所有素数都与k不同的那一部分；

这样可以考虑正向枚举所有1120内的素数，那么d[ i ] [ j ] 转移时剪掉当前素数k之后，状态d[ i -k ][ j-1 ]此时肯定只包含由比k小的素数组成的结；

#include <map>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 10000000
using namespace std;
typedef long long LL;

const int maxn = 1120;

vector<int> primes;
int vis[maxn+10];
void init_primes_table(){
memset(vis,0,sizeof(vis));
int m=sqrt(maxn+0.5);
for(int i=2;i<=m;i++)if(!vis[i])
   for(int j=i*i;j<=maxn;j+=i) vis[j]=1;

for(int j=2;j<=maxn;j++)if(!vis[j])
    primes.push_back(j);
}
int d[maxn+10][15];

int main()
{
    init_primes_table();
    memset(d,0,sizeof(d)); d[0][0]=1;
    int lim=primes.size();
    for(int i=0;i<lim;i++){
        for(int j=14;j>=1;j--){
            for(int k=maxn;k>=primes[i];k--){
            d[k][j]+=d[k-primes[i]][j-1];
            }
        }
    }
    int n,m;
    while(scanf("%d %d",&n,&m)==2){
            if(!n&&!m) break;
       printf("%d\n",d[n][m]);
    }
    return 0;
}