挑战28：验证歌德巴赫猜想，我的酷睿i7狂奔一小时。。。。。。

福华

我的想法很简单，也很直接，把一个数拆成两个，如果两个数都是质数，那就成立。
完整代码如下：
#include <stdio.h>
#include <stdlib.h>
int prime(int n)      /*定义函数prime，用于判断质数*/
{
    int i,f=1;
    for (i=2;i<n;i++)
    {
            if(n%i==0)
             {
             f=0;
             break;
             }
    }
    if(f==0)          return 0;
    else                return 1;   
}
int main()
{
printf("用于把一个数拆分成两个质数之和\n");
while(1)
    {
  int n,a,b,amount=0;
  scanf("%d",&n);
  for(a=2;a<=n/2;a++)
  {
  b=n-a;
   if(prime(a)&&prime(b))
   {
   printf("%d=%d+%d\n",n,a,b);
   amount++;
   }
  }   
  printf("总数=%d\n",amount);
  printf("\n");
    }
system("pause");
return 0;
}
CPU是酷睿i7,风扇轰鸣一小时多，结果倒是对的。
是我的算法要改进，还是这题本来就这么坑爹？
同学们有什么好方法啊？

Dsp

先弄一个数组放质数
然后用题目中的数减去一个质数
再判断差是不是质数
（直接扫一下数组里的质数）

福华

这样做似乎快一点
遇到性能瓶颈了

zhuzhu81998

检测质数那儿就慢了点吧？看看rosynirvana的吧！http://www.ahalei.com/forum.php? ... amp;_dsign=91ad725e

福华

脑洞大开，长见识

福华

对算法做了优化，改进后的完整代码如下：
[mw_shl_code=c,true]#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int prime(int n)
{
        int i,f=1;
    if(n%2==0||n==1)        return 0;
    else
    {
                for(i=3;i<=sqrt(n);i+=2)
        {
                        if(n%i==0)        {f=0;break;}
        }
        if(f==1) return 1;
        if(f==0) return 0;
    }
   
}
int main()
{
        printf("用于把一个数拆分成两个质数之和\n");
        while(1)
    {
                int n,a,b,amount=0;
                scanf("%d",&n);
                for(a=2;a<=n/2;a++)
                {
               
                        if(prime(a))
                        {
                                b=n-a;
                if(prime(b))
                                {
                printf("%d=%d+%d\n",n,a,b);
                                amount++;
                }
                        }
                }   
                printf("总数=%d\n",amount);
                printf("\n");
    }
        system("pause");
        return 0;
}
[/mw_shl_code]

福华

不到一分钟计算完成{:soso_e192:}

福华

之前就是慢在判断质数部分