hrb 2134 素数

分拆素数和
Time Limit: 1000 MS Memory Limit: 32768 K
Total Submit: 176(99 users) Total Accepted: 106(93 users) Rating: hrb 2134 素数hrb 2134 素数 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;
}

上一篇:最小的K个数:用快排的思想去解相关问题


下一篇:Ubuntu下配置ShadowS + Chrome