分拆素数和

Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 176(99 users) Total Accepted: 106(93 users) Rating:  Special Judge: No

Description

把一个偶数拆成两个不同素数的和，有几种拆法呢？

Input

每行包含一个正的偶数，其值不会超过10000，个数不会超过500。

Output

对应每个偶数，输出其拆成不同素数和的组数，每个结果占一行。

Sample Input

30 26

Sample Output

3 2

Source

2014暑假集训练习赛（7月30日）

打表即可

#include<stdio.h>
#include<string.h>
int prim[10001];
bool vis[10001];
int ans[10001];
int n;
void getprim(){
memset(vis,true,sizeof(vis));
int num=0;
for(int i=2;i<=n;i++){
if(vis[i]==true){
num++;
prim[num]=i;
}
for(int j=1;((j<=num)&&(i*prim[j]<=n));++j){
vis[i*prim[j]]=false;
if(i%prim[j]==0)
break;
}
}
}
int main(){
while(scanf("%d",&n)!=EOF){
memset(prim,0,sizeof(prim));
memset(ans,0,sizeof(ans));
int sum=0;
getprim();
for(int i=0;i<=n;i++){
if(prim[i]){
ans[prim[i]]=1;
}
}
for(int i=0;i<n/2;i++){
if(ans[i]&&ans[n-i])
sum++;
}
printf("%d\n",sum);
}
return 0;
}