liukairui @ 2019-07-12 23:37:24
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;
stack<int>ans;
bool is_z[20050],flag=false;
int zsb[2500],n,cur=0;
void dfs(int now,int rest,int summary){
if(summary>n)return;
if(now==cur-1&&(rest!=1||is_z[n-summary]==false))return;
if(rest==1&&is_z[n-summary]==true){ans.push(n-summary);return;}
if(rest==1&&is_z[n-summary]==false)return;
//边界
dfs(now,rest-1,summary+zsb[now]);
if(flag==true){ans.push(zsb[now]);return;}
dfs(now+1,rest-1,summary+zsb[now]);
if(flag==true){ans.push(zsb[now]);return;}
dfs(now+1,rest,summary);
if(flag==true){ans.push(zsb[now]);return;}
return;
}
int main(){
cin>>n;
//构造素数表
memset(is_z,true,sizeof(is_z));
for(int i=2;i<=sqrt(n*3);i++){
if(is_z[i]==false)continue;
for(int j=2;j*i<=n*3;j++)is_z[i*j]=false;
}
for(int i=2;i<=n;i++)if(is_z[i]==true)zsb[cur++]=i;
//dfs
for(int i=0;i<cur;i++){
dfs(0,3,0); //dfs(now,已经选了几个数,summary)
}
for(int i=0;i<3;i++){cout<<ans.top()<<" ";ans.pop();}
return 0;
}