首页 > 代码库 > HDU 5150 Sum Sum Sum 素数

HDU 5150 Sum Sum Sum 素数

2024-11-01 13:27:02   208人阅读

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
35 6 7110
 

 

Sample Output
120
 
难点是把：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 = 1001;bool flag[MAXN];int primes[MAXN], pi;void GetPrime_1(){    int i, j;    pi = 0;    memset(flag, false, sizeof(flag));    for (i = 2; i < MAXN; i++)        if (!flag[i])        {            primes[i] = 1;//素数标识为1            for (j = i; j < MAXN; j += i)                flag[j] = true;        }}int main(){    memset(primes,0,sizeof(primes));    GetPrime_1();    primes[1]=1;    int n;    while(scanf("%d",&n)!=EOF)    {        long long ans=0;        int a;        for(int i=0;i<n;i++)        {            cin>>a;            if(primes[a]==1)                ans+=a;        }        cout<<ans<<endl;    }    return 0;}

 

HDU 5150 Sum Sum Sum 素数


联系
我们