给定n(n≤100)个整数,求其中所有素数的和。
时间: 2023-05-25 09:04:50 浏览: 77
算法1:暴力枚举
遍历每个数,判断是否为素数,若是则加上该数。
时间复杂度:$O(n\sqrt{n})$,sqrt为判断素数的时间复杂度。
C++ 代码
```cpp
#include <iostream>
using namespace std;
bool isPrime(int x) // 判断x是否为素数
{
if (x < 2) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
int main()
{
int n;
cin >> n;
int sum = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (isPrime(x)) sum += x;
}
cout << sum << endl;
return 0;
}
```
算法2:线性筛
用线性筛找出1~N中的所有素数,然后遍历每个数,若是素数则加上该数。
时间复杂度:$O(n\log\log n)$。
C++ 代码
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int sum[N], primes[N], cnt;
bool st[N]; // st[x]表示x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
}
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main()
{
int n;
cin >> n;
get_primes(n);
int s = 0;
for (int i = 0; i < cnt; i++) {
s += primes[i];
}
cout << s << endl;
return 0;
}
```