啊哈磊_编程从这里起步

标题: 挑战28：验证歌德巴赫猜想，我的酷睿i7狂奔一小时。。。。。。 [打印本页]

作者: 福华 时间: 2015-6-21 21:43
标题: 挑战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 时间: 2015-6-25 09:07
先弄一个数组放质数
然后用题目中的数减去一个质数
再判断差是不是质数
（直接扫一下数组里的质数）

作者: 福华 时间: 2015-6-25 10:01
这样做似乎快一点
遇到性能瓶颈了

作者: zhuzhu81998 时间: 2015-6-25 20:03
检测质数那儿就慢了点吧？看看rosynirvana的吧！http://www.ahalei.com/forum.php? ... amp;_dsign=91ad725e

作者: 福华 时间: 2015-6-25 22:38
脑洞大开，长见识

作者: 福华 时间: 2015-6-27 20:14
对算法做了优化，改进后的完整代码如下：
[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]

作者: 福华 时间: 2015-6-27 20:15
不到一分钟计算完成{:soso_e192:}

作者: 福华 时间: 2015-6-27 20:17
之前就是慢在判断质数部分

欢迎光临啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)