HDU 1397 Goldbach's Conjecture

哥德巴赫猜想，注意不要重复统计分解得到的素数对，即((3,7))和((7,3))视为同一对。

const int N=35010;
int primes[N],cnt;
bool vis[N];
int n;

void init(int n)
{
    for(int i=2;i<=n;i++)
        if(!vis[i])
        {
            primes[cnt++]=i;
            for(int j=i;j<=n/i;j++)
                vis[i*j]=true;
        }
}

int main()
{
    init(1<<15);

    while(cin>>n && n)
    {
        int res=0;
        for(int i=0;i<cnt;i++)
        {
            int x=n-primes[i];
            if(x < primes[i]) break;
            if(!vis[x]) res++;
        }
        cout<<res<<endl;
    }

    //system("pause");
    return 0;
}