天上一颗蛋 @ 2017-11-03 20:42:46
#include<iostream>
#include<cstdlib>
using namespace std;
const int maxn=21000;
bool p[maxn];
int temp[3];
int biao[maxn];
int s;
int n;
int all;
void prime(int n){
for(int i=2;i<n;i++){
if(p[i]==0){
biao[s]=i;
s++;}
for(int j=0;j<s && i*biao[j]<n;j++){
p[i*biao[j]]=1;
if(i%biao[j]==0){
break;
}
}
}
}
void print(){
for(int i=0;i<3;i++){
cout<<temp[i]<<" ";
}
}
void dfs(int index,int num){
if(index>n)return;
if(num==3){
if(all==n){
print();
exit(0);
}
return;
}
if(all<n&&num<3){
temp[num]=biao[index];
all+=biao[index];
dfs(index,num+1);
all-=biao[index];
dfs(index+1,num);
}
}
int main(){
cin>>n;
prime(n);
dfs(0,0);//深搜超时#7 #10难过。。。
}by KillerXu @ 2017-11-04 21:34:19
想多了，别受题解和讨论影响，不过是二重循环+素数判断是绝对能过的，最慢不到0.1秒
by KillerXu @ 2017-11-04 21:36:01
其实，怎么说呢……好多人被这题折磨的死去活来
by KillerXu @ 2017-11-04 21:37:12
都是因为看到数据的原因，其实不是三重循环是可以过的
by 天上一颗蛋 @ 2017-11-04 21:54:56
为什么？？？
这不科学啊
by 天上一颗蛋 @ 2017-11-04 22:52:29
@许思远 还是不懂
枚举判断怎么会比打表快呢？
by KillerXu @ 2017-11-05 20:29:42
#include<stdio.h>
int ss(int n)
{
int i;
for(i=2;i<n;i++) if(n%i==0) return 1;
return 0;
}
int main()
{
int i,j,n,flag=0;
scanf("%d",&n);
for(i=2;i<=n/2;i++)
{
for(j=2;j<n;j++)
{
if(ss(i)==0&&ss(j)==0&&ss(n-(i+j))==0&&n-i-j!=0)
{
printf("%d %d %d",i,j,n-(i+j));
flag=1;
}
if(flag) break;
}
if(flag) break;
}
return 0;
}