hdu 1397

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1397

题意：给一个偶数，求可以表示为多少对素数对的和。

mark：最大范围是2^15 = 32768。打素数表，然后枚举。理论上会TLE，但是水过了。

代码：

# include <stdio.h>


int IsPrime[40010] ;


void init()
{
    int i, j ;
    for (i = 0 ; i <= 40000 ; i++)
        IsPrime[i] = 1 ;
    for (i = 2 ; i <= 200 ; i++) if (IsPrime[i])
        for (j = i * i ; j <= 40000 ; j+= i) IsPrime[j] = 0 ;
}


int main ()
{
    int i, ans, n ;
    init() ;
    while (~scanf ("%d", &n) && n)
    {
        ans = 0 ;
        for (i = 2 ; i <= n/2 ; i++)
            if (IsPrime[i] && IsPrime[n-i]) ans++ ;
        printf ("%d\n", ans) ;
    }
    return 0 ;
}