选择K个质数,使它们的和等于N。问有多少种方案?
例如,n=24,
k=2时有3种方案:5+19=7+17=11+13=24
#include <iostream> #include <cstring> #include <cmath> #include <algorithm> using namespace std ; const int M =1e6+33; int b[M],c[M],tot; int n,m,f[2000][20]; void init(int top){ memset(b,1,sizeof b); b[1]=0; int i,j; for(i=2;i<=top;i++){ if(b[i]) c[++tot]=i; for(j=1;j<=tot&&i*c[j]<=top;j++){ b[i*c[j]]=0; if(i%c[j]==0) break; } } } void sov(){ int i,j,k; memset(f,0,sizeof f); f[0][0]=1; for(i=1;i<=tot;i++) for(j=1200;j>=c[i];j--) for(k=1;k<=n;k++) f[j][k]+=f[j-c[i]][k-1]; cout<<f[m][n]<<endl; } signed main(){ init(3000); while(cin>>m>>n,n&&m) sov(); }