ZOJ Problem Set – 1657 Goldbach's Conjecture

长时间不做算法题了，这么简单的题目都然给我纠结了那么久，尴尬……先把题目贴出来，稍作分析，相信小孩子都可以看得懂了。

原题：

Goldbach's Conjecture

---

Time Limit: 1 Second      Memory Limit: 32768 KB

---

Goldbach's Conjecture: For any even number n greater than or equal to 4, there exists at least one pair of prime numbers p1 and p2 such that n = p1 + p2.

This conjecture has not been proved nor refused yet. No one is sure whether this conjecture actually holds. However, one can find such a pair of prime numbers, if any, for a given even number. The problem here is to write a program that reports the number of all the pairs of prime numbers satisfying the condition in the conjecture for a given even number.

A sequence of even numbers is given as input. Corresponding to each number, the program should output the number of pairs mentioned above. Notice that we are interested in the number of essentially different pairs and therefore you should not count (p1, p2) and (p2, p1) separately as two different pairs.

Input

An integer is given in each input line. You may assume that each integer is even, and is greater than or equal to 4 and less than 2^15. The end of the input is indicated by a number 0.

Output

Each output line should contain an integer number. No other characters should appear in the output.

Sample Input

6
10
12
0

Sample Output

1
2
1

---

Source: Asia 1998, Tokyo (Japan)

这道题目，说难不难，说简单，对初学的我来说看来也不是那么一回事儿。题意很明确，就是要把一个偶数分解成两个素数的和的问题。求一个给定的偶数，可以分解成多少对符合题意的素数对。看到题目的第一反应，自然是先建立一张素数表，这样做显然是效率最高的。接下来的差异就在如何建立这张表了。我用了一个筛子，把要求范围内的素数全部筛选出来了，然后在进行操作。由于一个数N分解成两个书之后，在循环中可以得到（a，b）和（b，a）这样两队，遵照题意，这样的两队只能算一对。一个数字N显然有N=(N/2-X)+(N/2+X)。于是乎，我们只要搜索偶数N的小于一半的符合题意的素数即可。即存在素数n，使得N-n也是素数，其中n<=N/2。由此，得出如下代码：

  #include "stdafx.h"
  
  #include<iostream>
  #include<bitset>
  #include<cmath>
  
  using namespace std;
  
  const int PRIME_NUM = 32768; //pow(2.0,15);
  
  bitset<PRIME_NUM> Primes;//用筛选法建立素数表
  void InitialPrimers()
  {
    Primes.set();
    for(int i = 4; i < Primes.size();i +=2)
    {
      Primes.reset(i);
    }
    for(int i = 3;i < Primes.size(); i +=2)
    {
      if(Primes.test(i))
      {
        for(int j = i*i;j < Primes.size();j += 2*i)
        {
          Primes.reset(j);
        }
      }
    }
  }
  
  int main(void)
  {
    InitialPrimers();
    for(int n;cin>>n && n;)
    {
      int sum = 0;
      for(int i = 2;i <= n/2;i++)
     {
       if(Primes.test(n - i) && Primes.test(i))//测试符合条件的素数对
        {
         sum ++;
        }
     }
     cout<<sum<<endl;
    }
   return 0;
 }