c++解决:题目描述 皮皮正在做一道非常难的数学题,经常需要知道一些质数,每次会询问两个数 a,b,想要知道第 a 个到第 b 个质数的和是多少?你能帮帮忙吗? 【输入格式】 输入共 1 行: 两个空格隔开的正整数,表示询问的是第 a 个到第 b 个质数。 【输出格式】 输出共 1 行: 第一行,一个整数表示第 a 个到第 b 个质数的和。 【输入输出样例#1】 输入#1 复制 5 8 输出#1 复制 60 【说明提示】 第 5~8 个质数分别是:11 13 17 19,和为 60。 【数据范围】 1 ≤ a < b ≤ 1000;第 1000 个质数是 7919。
时间: 2024-03-24 08:41:22 浏览: 98
以下是 C++ 的代码实现:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e4 + 10; // N 为预处理的最大质数数量
bool st[N]; // st[i] 表示 i 是否为质数
vector<int> primes; // primes 存储所有的质数
int main() {
int a, b;
cin >> a >> b;
// 预处理质数
for (int i = 2; i < N; i++) {
if (!st[i]) {
primes.push_back(i);
for (int j = i + i; j < N; j += i) {
st[j] = true;
}
}
}
int sum = 0;
for (int i = a - 1; i < b; i++) {
sum += primes[i];
}
cout << sum << endl;
return 0;
}
```
首先,我们需要预处理出一定范围内的所有质数。这里我们使用线性筛法来预处理,具体过程就不再赘述了,可以自行查阅相关资料。
预处理完成后,我们就可以很方便地计算第 a 个到第 b 个质数的和了。只需要遍历 primes 数组中第 a-1 个(注意数组下标从 0 开始)到第 b-1 个质数,将它们的和累加到 sum 变量中即可。
最后输出 sum 即可。
阅读全文