学步园

题目连接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=13&problem=1109&mosmsg=Submission+received+with+ID+8770141

题目已经把题意说的很清楚了

就是把一个数n拆成4个质数的和

数据规模是10^7，所以直接打一个10^7的素数表是可行的（大概500MS就可以完成）

思路：
首先要明确以下观点：

当n小于等于7的时候不可能有解

这个道理很显然，因为当n==8的时候可以拆成2+2+2+2(四个最小的素数了)

所以n<8不可能在存在分解方法

故：第一步为判断n是否大于等于8

那么剩下就是证明n大于等于8的时候是否一定存在可行解

答案是肯定的！！！！

我的证明非常简单（之前的方法确实是想复杂了）

当n为一个偶数的时候，那么他一定可以分解为两个偶数的和

而在假设哥德巴赫猜想成立的条件下，偶数是一定可以分解为两个质数的和的。所以，n也一定能够分解为4个素数的和

然后就是n为奇数的时候

当n为奇数，我们可以把它拆分为两个偶数和一个1的和

进一步猜想，我们一定可以写成2+3+偶数的形式（这么做是有原因的！！主要是为了实现方便）

我的代码：

#include<stdio.h><br /> #include<string.h></p> <p>#define maxn 10000001</p> <p>bool flag[maxn];<br /> int prime[1000000];<br /> int num=0;</p> <p>void init()<br /> {<br /> unsigned long i,j;<br /> memset(flag,0,sizeof(flag));<br /> flag[1]=true;<br /> flag[0]=true;<br /> for(i=2;i<maxn;i++)<br /> {<br /> if(!flag[i])<br /> {<br /> prime[num++]=i;<br /> for(j=i*i;j<maxn;j=j+i)<br /> flag[j]=true;<br /> }<br /> }<br /> }</p> <p>int main()<br /> {<br /> int i,a,b,c,d,n;<br /> init();<br /> while(scanf("%d",&n)!=EOF)<br /> {<br /> if(n<=7)<br /> {<br /> printf("Impossible./n");<br /> continue;<br /> }<br /> if(n&1)<br /> {<br /> a=2;<br /> b=3;<br /> n=n-5;<br /> for(i=0;i<num;i++)<br /> {<br /> if(!flag[n-prime[i]])<br /> {<br /> c=prime[i];<br /> d=n-prime[i];<br /> break;<br /> }<br /> }<br /> printf("%d %d %d %d/n",a,b,c,d);<br /> }<br /> else<br /> {<br /> a=2;<br /> b=2;<br /> n=n-4;<br /> for(i=0;i<num;i++)<br /> {<br /> if(!flag[n-prime[i]])<br /> {<br /> c=prime[i];<br /> d=n-prime[i];<br /> break;<br /> }<br /> }<br /> printf("%d %d %d %d/n",a,b,c,d);<br /> }<br /> }<br /> return 0;<br /> }