Description： 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. There can be many such numbers. 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 215. 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

1
2
3
4
6
10
12
0

Sample Output

1
2
3
1
2
1

这道题是一道暴力题， 但是有一个优化的地方就是将已经计算过的素数记录下来，这样应该不会超时。另一个需要注意的地方就是如何判断一个数是素数。这里用的是试除法。

**试除法**：测试n是否为素数的最基本方法为试除法。此一程序将n除以每个大于1且小于等于n的平方根之整数m。若存在一个相除为整数的结果，则n不是素数；反之则是个素数。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cmath>
using namespace std;

int prime_ary[65535+5]={0};  // 记录素数

bool is_prime_number(int n) {
    if(n==0 || n==1)
    return false;
    
    bool flag=true;
    for(int i=2;i<=sqrt((double)n);i++)
    {
        if(n%i==0)
            flag=false;
    }
    return flag;
}

int calc_pair_num(int n){
    int cnt=0;
    // 这里要预先计算到n的素数 
    for(int i=n;prime_ary[i]==0 && i>=0;i--){
        if(is_prime_number(i)) 
            prime_ary[i]=2;  //2表示i是素数
        else
            prime_ary[i]=1; //1表示i不是素数，0表示没有判断过i是否是素数
    }
    
    int last=n/2+1;  //用于避免重复计算,因为1+2和2+1算作一种情况
    for(int i=2;i<last;i++){
        if(prime_ary[i]==2 && prime_ary[n-i]==2){
            cnt+=1;
            last=n-i;
        }
    }
    return cnt;
}

int main(){
    int n;
    while(cin>>n) {
        if(n==0) break;
        cout<<calc_pair_num(n)<<endl;
    }
    return 0;
}

参考文献：