这道题目的URL:http://acm.hdu.edu.cn/showproblem.php?pid=1397
这道题目的解题要点是先用筛选法求出所有给定范围内的素数,然后哈希法查找。
这是我的AC代码:
#include<iostream>
using namespace std;
const int Max = (1<<15) + 10;
bool prime[Max];
void calcPrime()
{
memset(prime, true, sizeof(prime));
for(int i=2; i<Max; i++)
{
for(int j=i*2; j<Max; j+=i) prime[j] = false;
}
prime[0] = prime[1] = false;
}
int main()
{
int num, cnt;
calcPrime();
while(scanf("%d", &num) && num)
{
cnt = 0;
for(int i=num/2; i<num; i++)
if(prime[i] && prime[num-i]) cnt ++;
printf("%d\n", cnt);
}
system("pause");
return 0;
}