这是OJ平台上的一道题

 题目如下：

验证歌德巴赫猜想

 要求：Time Limit: 400/200 MS (Java/Others)     Memory Limit: 32768/5000 K (Java/Others)


我自己写了一份代码，用的是筛选法求素数，但提交后还是Time Limit Exceeded，是筛选法还不够优化还是我后面那个输出的方法不够好，或者我的代码中有哪些不足或不妥的地方，请各位大神不吝指出，谢谢

 以下是本人的代码：

#include<stdio.h>

 int main()
 {
     int n,i,t,p,q,a[10001],k,w;

     while(scanf("%d",&n)==1)//用筛选法求出所有素数
    {
         t=1;
         a[1]=2;
         for(i=3; i<=n; i++)
         {
             if(i%2!=0)
             {
                 t++;
                 a[t]=i;
             }
         }

         for(p=1; p<t; p++)
         {
             if(a[p]!=0)
                 for(q=p+1; q<=t; q++)
                 {
                     if(a[q]%a[p]==0)
                         a[q]=0;
                 }
         }

         k=0;

         if(t%2!=0)//将a[t]一分为二，前部分为较小数，后部分为较大数
            w=t/2+1;
         else
             w=t/2;

         for(p=w; p>=1; p--)//思路是"用较小数中的最大数"加上"较大数中的最小数"，不满足判断条件的话，较大数中的最小数再往后变大
        {
             if(a[p]!=0)
             {
                 for(q=w; q<=t; q++)
                     if(a[q]!=0)
                     {
                         if(a[p]+a[q]==n)
                         {
                             printf("%d %d\n",a[p],a[q]);
                             k=1;
                             break;
                         }
                     }
             }

             if(k==1)
                 break;
         }
     }

     return 0;
 }

首先你这个如果算筛法也不是最快的筛法，你先用一重循环筛出奇数，再用两重循环嵌套筛出素数，里面使用了取余数运算，比较耗时，最快的运算就是加减；其次你每次都重复找素数，这样会降低效率，应该一次建立10000以内的素数表，以后只要用即可。我的代码如下，你可以试下超时没有。

#include<stdio.h>
int main()
{
    int n,i,t;
    char a[10000]={0};
    for(i=2;i<10000;i++)if(!a[i])for(t=i+i;t<10000;t+=i)if(!a[t])a[t]=1;  //建立10000以内的素数表
    while(scanf("%d",&n))
    {
        if(!(n%2))  //保证输入的是偶数
        {
            t=0;
            for(i=2;i<n&&i<=n-i;i++)  //找素数同时保证左边素数小于右边素数
                if(!a[i]&&!a[n-i])t=i;  //记录最接近的两个素数位置
            if(t)printf("%d %d\n",t,n-t);
        }
    }
    return 0;
}

 

[ 本帖最后由 wmf2014 于 2015-5-7 01:29 编辑 ]

我以前写的  也没考虑算法啥的

#include <stdio.h>

int issh(int x)
{ 
    //返回1 表示是一个素数
    if(x<=1) return 0;
    if(x>1)    for(int i=2;i<x;i++) if(x%i==0) return 0;
    return 1;
}

int main()
{
    int i,j;
    int k=0;
    for(j=4;j<9999;j+=2)
    {
        for(i=1;i<j;i++)
        {
            if(issh(i)==1 && issh(j-i)==1) 
            {
                printf("%d=%d+%d\n",j,j-i,i);
                k++;
                break;
            }
        }
        if(k==0) printf("%d不能被分解成2个素数之和.\n",j);
    }
    return 0;
}

看了好多贴都有二楼的回答，二楼的思路总是那么清晰啊，求带。

谢谢指点

#include "stdio.h"
int main()
{
    int a[10000],i,j;
    for(i=1;i<10000;i++)
        a[i]=i;
    for(i=2;i<100;i++)
        for(j=i+1;j<10000;j++)
        {
            if((a[i]!=0)&&(a[j]!=0))
            if(a[j]%a[i]==0)
                a[j]=0;
        }
    for(i=2;i<10000;i++)
        if(a[i]!=0)
            printf("%d\t",a[i]);
   
    return 0;
}


这两种筛法有什么区别吗？