异想天开

What's the true meaning of light, Could you tell me why

素数求和问题

日期:2015-05-07 14:06:58
  
最后更新日期:2015-05-07 15:52:57
简单
http://acm.nyist.net/JudgeOnline/problem.php?pid=22
描述
现在给你N个数(0输入
第一行给出整数M(0每组测试数据第一行给你N,代表该组测试数据的数量。
接下来的N个数为要测试的数据,每个数小于1000
输出
每组测试数据结果占一行,输出给出的测试数据的所有素数和
样例输入
3
5
1 2 3 4 5
8
11 12 13 14 15 16 17 18
10
21 22 23 24 25 26 27 28 29 30
样例输出
10
41
52
解析:
素数求和,需要判断素数的次数多,那么可以用个hash来判断。程序开始计算出10000以内的所有的素数,后面求和就是。
[code lang="cpp"]
#include<stdio.h>
#include <string.h>
#define ARRAY_LEN 1000
#define WORD_LEN 32
unsigned int p[ARRAY_LEN];
#define LEN ARRAY_LEN*WORD_LEN
int cal(){
int i=2,j=0,k,m;
memset(p,0xffffffff,sizeof(p));
p[0]=0xfffffffc;
for (i=2;i<LEN;i++){
k=i/WORD_LEN;
m=1<<(i%WORD_LEN);
if (p[k]&m){
for (j=i+i;j<LEN;j+=i){
k=j/WORD_LEN;
m=1<<(j%WORD_LEN);
if (p[k]&m){
p[k]=p[k]&(~m);
}
}
}
}
return 0;
}

int cal1(){
int i=2,j=0,k;
unsigned char m;
memset(p,0xff,sizeof(p));
p[0]=0xfc;
for (i=2;i<LEN;i++){
k=i/WORD_LEN;
m=1<<(i%WORD_LEN);
if (p[k]&m){
for (j=i+i;j<LEN;j+=i){
k=j/WORD_LEN;
m=1<<(j%WORD_LEN);
if (p[k]&m){
p[k]=p[k]&(~m);
}
}
}
}
return 0;
}

int sovle(){
int i=0,tmp=0,t=0,n=0,sum=0, x,y;
cal();

scanf("%d",&t);
while(t--){
sum=0;
scanf("%d",&n);

for (i=0;i<n;i++){
scanf("%d",&tmp);
x=tmp/WORD_LEN;
y=1<<(tmp%WORD_LEN);
if (p[x]&y){
sum+=tmp;
}
}

printf("%d ",sum);
}
return 0;
}

int main()
{
sovle();
return 0;
}
[/code]