HDU 2098 分拆素數和

把一個偶數拆成兩個不同素數的和，有幾種拆法呢？

Input

輸入包含一些正的偶數，其值不會超過10000，個數不會超過500，若遇0，則結束。

Output

對應每個偶數，輸出其拆成不同素數的個數，每個結果占一行。

Sample Input

30
26
0      

Sample Output

3

2

#include<cstdio>
const int N=1e4+10;
int f[N],p[N],t,n;

void init()
{
  f[1]=1; t=0;
  for (int i=2;i<N;i++)
  {
    if (!f[i]) p[t++]=i;
    for (int j=0;j<t&&p[j]*i<N;j++)
    {
      f[p[j]*i]=1;
      if (i%p[j]==0) break;
    }
  }
}

int main()
{
  init();
  while (~scanf("%d",&n),n)
  {
    int cnt=0;
    for (int i=0;i<t;i++)
    {
      if (p[i]+p[i]>=n) break;
      if (!f[n-p[i]]) cnt++;
    }
    printf("%d\n",cnt);
  }
  return 0;
}