/*题目大意：
在一个由素数组成的数列 2,3,5,7......
定义超级素数，数列中的第k项为超级素数当且仅当k也为素数
给定n
如果n能被超级素数的和所表示
输出最少要多少个超级素数，以及这些超级素数
否则输出impossible
暴力找出超级素数,跑完全背包即可。*/
|
|
/**********************
* author:crazy_石头
* Pro:SGU 116
* algorithm:dp
* Time:15ms
* Judge Status:Accepted
***********************/
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
#define LL long long
#define rep(i,h,n) for(int i=(h);i<=(n);i++)
#define ms(a,b) memset((a),(b),sizeof(a))
#define INF 1<<29
const int maxn=10000+20;
int prime[maxn],check[maxn],tot=0;
int ans[maxn],cnt=0,dp[maxn],way[maxn];
inline void get_prime()
{
memset(check,0,sizeof(check));
for (int i=2;i<maxn;i++)
{
if(!check[i])prime[++tot]=i;
for (int j=i+i;j<maxn;j+=i)
check[j]=1;
}
}
inline void init()
{
get_prime();
for (int i=2;i<=tot;i++)
if (check[i]==0)
ans[++cnt]=prime[i];
memset(way,0,sizeof(way));
for (int i=1;i<maxn;i++)
dp[i]=INF;
dp[0]=0;
}//预处理；
int main()
{
init();
int n;
scanf("%d",&n);
//完全背包；
for(int i =1;i<=cnt;i++)
{
for(int j=ans[i];j<=n;j++)
{
if (dp[j-ans[i]]+1<dp[j])
{
dp[j]=dp[j-ans[i]]+1;
way[j]=j-ans[i];
}
}
}
if(dp[n]<INF)
{
printf("%d\n",dp[n]);
int tmp=n;
for (int i=1;i<=dp[n]-1;i++) {
printf("%d ",tmp-way[tmp]);
tmp=way[tmp];
}
printf("%d\n",tmp);
}
else puts("0");
return 0;
}