hdu 5150 Sum Sum Sum 水

Sum Sum Sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description

We call a positive number X P-number if there is not a positive number that is less than X 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 N(1≤N≤1000). The second line contains N 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

Source

BestCoder Round #24

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
const int N=2e5+,M=1e6+,inf=1e9+,mod=1e9+;
const ll INF=1e18+;
int prime(int n)
{
    if(n<=)
    return ;
    if(n==)
    return ;
    if(n%==)
    return ;
    int k, upperBound=n/;
    for(k=; k<=upperBound; k+=)
    {
        upperBound=n/k;
        if(n%k==)
            return ;
    }
    return ;
}
int flag[];
int main()
{
    int n,x;
    for(int i=;i<=;i++)
    flag[i]=prime(i);
    flag[]=;
    while(~scanf("%d",&n))
    {
        int ans=;
        for(int i=;i<=n;i++)
        {
            scanf("%d",&x);
            if(flag[x])
            ans+=x;
        }
        printf("%d\n",ans);
    }
    return ;
}