Chinaunix首页 | 论坛 | 博客
  • 博客访问: 474721
  • 博文数量: 59
  • 博客积分: 345
  • 博客等级: 二等列兵
  • 技术积分: 1380
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-18 22:44
个人简介

to be myself

文章分类

全部博文(59)

文章存档

2017年(5)

2013年(47)

2012年(3)

2011年(4)

分类: C/C++

2013-03-02 17:07:46


点击(此处)折叠或打开

  1. #include <stdio.h>

  2. typedef unsigned int uint;

  3. int IsPrime(uint a)
  4. {
  5.   uint i;
  6.   if(1 == a)
  7.   {
  8.       return 0;
  9.   }
  10.   for(i=2;i*i<=a;i++)
  11.   {
  12.       if(0 == a % i)
  13.       {
  14.           return 0;
  15.       }
  16.   }
  17.   return 1;
  18. }

  19. int main()
  20. {
  21.   freopen("in.txt", "r", stdin);
  22.   uint m, i, j;
  23.   while(scanf("%u", &m)==1&&m!=0)
  24.   {
  25.       i=2;
  26.       while(!IsPrime(m-i))
  27.       {
  28.           i++;
  29.           while(!IsPrime(i))
  30.           {
  31.               i++;
  32.           }
  33.       }
  34.       printf("%d = %d + %dn", m, i, m - i);
  35.   }
  36.   return 0;
  37. }

刚开始准备又搞个10W以内的素数表,那样多快,可惜POJ不让提交,呵呵。
但第一次提交还是TLE,为什么?想多了。多了一个找m 的循环,以为先找到比m小且最接近的m 的素数往小的枚举。找到m -i 的那个也是素数就是差最大的两个能组成m 的odd prime 了。其实找最接近且小于m 的素数是多余的,从2往后枚举不就OK了。另外,还没有证明歌德巴赫的猜想是错的,所以,那个"Goldbach's conjecture is wrong." 也不用了。水题,增加信心。

2011-03-13 16:57 发表于百度空间,今搬至CU。

阅读(1059) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~