很SB的完全背包问题阿。。。
P.S
由于我沙茶。。素数判定居然写错了。。还调了半天。。
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=1000;
int Q,Ps[maxn],cnt=0,snt=0;
bool isprime(int p)
{
if(p==2) return true;
if(p%2==0) return false;
for(int i=3,j=9;j<=p;i+=2,j=i*i)
if(p%i==0) return false;
return true;
}
void init()
{
cin>>Q;
cnt=1;
for(int i=3;i<=Q;i++)
if( isprime(i) )
{
cnt++;
if(isprime(cnt))
{
Ps[snt++]=i;
}
}
}
bool G[maxn*10]={0};
int F[maxn*10]={0};
int P[maxn*10]={0};
int DP(int x)
{   
if(G[x]) return F[x];
G[x]=true;
for(int i=0;i<snt;i++) if(x>=Ps[i])
if(DP(x-Ps[i])<F[x])
{
F[x]=F[x-Ps[i]];
P[x]=Ps[i];
}
F[x]++;return F[x];
}
bool cmp(const int& x,const int& y)
{ return x>y;}
void print(int x)
{
int ans[maxn],cnt=0;
if(P[x]==0) {return;}
while(x)
{
ans[cnt++]=P[x];
x-=P[x];
}
sort(ans,ans+cnt,cmp);
cout<<ans[0];
for(int i=1;i<cnt;i++)
cout<<" "<<ans[i];
}
int main()
{
init();for(int i=0;i<=Q;i++) F[i]=~0U>>3;
F[0]=0;G[0]=true;
if( DP(Q)>10000 )
{
cout<<0<<endl;
}else
{
cout<<DP(Q)<<endl;
print(Q);
}
}