HDU 5150 Sum Sum Sum

Description

We call a positive number   P-number if there is not a positive number that is less than   and the greatest common divisor of these two numbers is bigger than 1. Now you are given a sequence of integers. You task is to calculate the sum of P-numbers of the sequence.

Input

There are several test cases. In each test case: The first line contains a integer  . The second line contains   integers. Each integer is between 1 and 1000.

Output

For each test case, output the sum of P-numbers of the sequence.

Sample Input

3 5 6 7 1 10

Sample Output

12

0

题意：给一组数，求其中是P-number的数的和（P-number指的是一个数X，所有比它小的数跟它的最大公约数不超过1，也就是所有的素数和1）.

本鶸：WA：2次

AC代码：

 

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; const int pmax=1e5+10; const int vmax=1e6+10; int prime[pmax],vis[vmax],psize=0; void getprime() { memset(vis,0,sizeof vis); vis[0]=vis[1]=1; for(int i=2;i<sqrt(vmax+0.5);i++) if(!vis[i]) for(int j=i*i;j<vmax;j+=i) vis[j]=1; for(int i=2;i<vmax;i++) if(!vis[i]) prime[psize++]=i; } int main() { getprime(); vis[1]=0; int N,a; while(scanf("%d",&N)!=EOF) { int sum=0; for(int i=0;i<N;i++) { scanf("%d",&a); if(!vis[a]) sum+=a; } printf("%d\n",sum); } return 0; }