HDU 5150 Sum Sum Sum 素数

Sum Sum Sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 290    Accepted Submission(s): 194

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

难点是把：primes[1]=1;

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;

const int MAXN = ;
bool flag[MAXN];
int primes[MAXN], pi;
void GetPrime_1()
{
    int i, j;
    pi = ;
    memset(flag, false, sizeof(flag));
    for (i = ; i < MAXN; i++)
        if (!flag[i])
        {
            primes[i] = ;//素数标识为1
            for (j = i; j < MAXN; j += i)
                flag[j] = true;
        }
}

int main()
{
    memset(primes,,sizeof(primes));
    GetPrime_1();
    primes[]=;
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        long long ans=;
        int a;
        for(int i=;i<n;i++)
        {
            cin>>a;
            if(primes[a]==)
                ans+=a;
        }
        cout<<ans<<endl;
    }
    return ;
}