/*一开始dp[1121][15],数组开小了，从1117 开始就会出错了，为什么呢？*/

#include<cstdio>
#include<cstring>
bool f[1130];
__int64 i,j,jmax,a,b,t[200],dp[1130][15];
int main()
{
    memset(f,true,sizeof(f));
    f[1]=f[0]=false;
    for(i=2;i*i<=1130;i++)
        if(f[i])
        {
            for(j=i+i;j<=1130;j+=i)f[j]=false;
        }
        
    for(j=0,i=2;i<=1130;i++)
        if(f[i])t[j++]=i;
        
    while(scanf("%d%d",&a,&b))
    {
        if(a+b==0)break;
        
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;

        for(j=0;t[j]<=a;j++)
            for(jmax=a;jmax>=t[j];jmax--)
                for(i=1;i<=b;i++)
                //for(i=b;i>=1;i--)  不是dp表还没填，就dp[0][0]=1,其余的都是0吗？
                //我就产生问题了，首先这个写法为什么是对的，还有这个运行还比前者快些，为什么
                    dp[jmax][i]+=dp[jmax-t[j]][i-1];
        printf("%I64d\n",dp[a][b]);
    }
    return 0;
}

• Re:在做这题时遇到了几个问题，在这希望一起能帮我解决下吧 (28) kyxyljb 2009-08-10 14:50:16