Q686: Goldbach's Conjecture(II)

/*
    這題和 Q543類似
    只是要算有幾個解
    所以只要算到 N/2 即可(要相異解)
    但注意 n = 4 = 2+2
    這是和Q543不一樣的地方
    n的限制是從4到32767

    Run time: 0.000
*/
#include <stdio.h>
#define N 32768
int main()
{
    int n;
    int i, j;
    bool arr[N+1];

    for ( i = 3; i < N; i+=2)
        arr[i] = true;

    for ( i = 3; i*i < N; i+=2)
        if (arr[i])
           for ( j = 3*i; j < N; j+=i)
               if (arr[j])
                  arr[j] = false;


    while (scanf("%d", &n))
    {
        if (!n) break;

        int cnt = 0;
        if (n == 4)
        {
            printf("1\n");
            continue;
        }

        for ( i = 3; i <= n/2; i+=2)
        {
            if (arr[i])
            {
                j = n-i;
                if (arr[j])
                    cnt++;
            }
        }
        printf("%d\n", cnt);
    }
}