SGU 116 – Prime Generate & DP

/* Prime Generate and DP
 * Good Pratice, remember to see the output format!
 */
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
bool is[10005]={0};
int  superPrime[205],pn=0,spn=0;
int  n,k;
 
bool dp[10005]={0};
int  num[10005],pre[10005],ans[10005],an=0;
 
void getAns(int now, int before)
{
	if(now==0) return;
	ans[an++]=now-before;
	getAns(before,pre[before]);
}
 
int main()
{
	/* Prime Gen */
	is[0]=is[1]=true;
	for(int i=2;i<=10000;i++)
		if(!is[i]) {
			++pn;
			if(!is[pn]) superPrime[spn++]=i;
			for(int j=i+i;j<=10000;j+=i) is[j]=true;
		}
 
	/* DP Start */
	scanf("%d",&n);
	dp[0]=true;
	num[0]=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<spn;j++)
		{
			k=i-superPrime[j];
			if(k>=0 && dp[k]) {				
				if(dp[i]==false) { dp[i]=true; num[i]=num[k]+1; pre[i]=k; }
				else if(num[i] > num[k]+1) { num[i]=num[k]+1; pre[i]=k; }
			} else 
			if(k<0) break;
		}
 
	/* Output*/
	if(dp[n]) {
		printf("%d\n",num[n]);
		an=0;
		getAns(n,pre[n]);
		sort(ans,ans+an);
		for(int i=an-1;i>=0;i--)
			if(i) printf("%d ",ans[i]);
			else printf("%d\n",ans[i]);
	} else puts("0");
	return 0;
}