1810 - 素数求和问题
现在给你N个数（0<N<1000），现在要求你写出一个程序，找出这N个数中的所有素数，并求和。
Input
第一行给出整数M(0<M<10)代表多少组测试数据
每组测试数据第一行给你N，代表该组测试数据的数量。
接下来的N个数为要测试的数据，每个数小于1000000
Output
每组测试数据结果占一行，输出给出的测试数据的所有素数和。
Examples
Input
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
Output
10 41 52
Solution C
#include <stdio.h> #include <string.h> #define MAX 1000004 char isPrime[MAX]; int main(){ int total, n, i, j, N, sum; memset(isPrime, 1, MAX); isPrime[0] = 0; isPrime[1] = 0; for(i = 4; i < MAX; i+=2) isPrime[i] = 0; for(i = 3; i < MAX; i+=2){ if(!isPrime[i]) continue; for(j = i + i; j < MAX; j+=i){ isPrime[j] = 0; } } scanf("%d", &total); while(total--){ scanf("%d", &n); for(i = sum = 0; i < n; i++){ scanf("%d", &N); if(isPrime[N]) sum += N; } printf("%d\n", sum); } return 0; }
Solution C++
#include <iostream> #include <cstdio> using namespace std; const int N=1000000; int i,j; int t,a,n,s; bool f[N+1]; void work() { for(i=3;i<=N;i++) { if(!f[i]) for(j=3*i;j<=N;j+=2*i) f[j]=1; } } int main() { work(); scanf("%d",&t); while(t--) { scanf("%d",&n); s=0; for(i=1;i<=n;i++) { scanf("%d",&a); if(a==1||(a>2&&a%2==0)) continue; if(!f[a]) s+=a; } printf("%d\n",s); } return 0; }