【poj】2262 Goldbach's Conjecture

#include <stdio.h>

typedef unsigned int uint;

int IsPrime(uint a)
{
  uint i;
  if(1 == a)
  {
      return 0;
  }
  for(i=2;i*i<=a;i++)
  {
      if(0 == a % i)
      {
          return 0;
      }
  }
  return 1;
}

int main()
{
  freopen("in.txt", "r", stdin);
  uint m, i, j;
  while(scanf("%u", &m)==1&&m!=0)
  {
      i=2;
      while(!IsPrime(m-i))
      {
          i++;
          while(!IsPrime(i))
          {
              i++;
          }
      }
      printf("%d = %d + %dn", m, i, m - i);
  }
  return 0;
}

刚开始准备又搞个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。