杭电acm1397

http://acm.hdu.edu.cn/showproblem.php?pid=1397

这题跟UVA上面的一题是基本一样的，但是hdoj上的时间限制得更狠，暴力来的话会超时，应该先将2到2的15次的数都打上标识，然后从2开始，循环到输入的那个数n，分别去判断那对数，刚开始是打算一次把所有的数都打表，后来发现时间太特么久了

View Code

 1 #include<stdio.h>
 2 #include<math.h>
 3 int yanzheng(int a)
 4 {
 5  int i;
 6  for(i=2;i<=sqrt(a);i++)
 7    { 
 8    if(a%i==0)
 9       return 0;
10    }
11  return 1;
12 }
13 int main()
14 {
15  int n,j,js,i,s;
16  int ans[33000];
17  for(j=2;j<33000;j++)
18     ans[j]=yanzheng(j);
19  while(scanf("%d",&n)&&n)
20       {
21       js=0;
22       for(i=2;i<=n/2;i++)
23       if(ans[i]&&ans[n-i])
24          js++;
25        printf("%d\n",js);  
26       }
27  return 0;
28 }