题面
2,3,5,7,11,13,… 是素数序列。 类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。
上边的数列公差为 30，长度为 6。
2004 年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。 这是数论领域一项惊人的成果！
有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：
长度为 10 的等差素数列，其公差最小值是多少？
题解
素数筛，枚举
利用 埃式筛 预处理出素数数组，然后暴力枚举公差和首项，注意首项必须为素数，则直接枚举素数数组即可。
具体见代码。
答案：
210
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
bool p[N];
vector<int> primes;
//素数筛
// 将 1 - n 中的所有素数存入 primes 中，并且 p[i] 表示 i 是否为素数
void do_primes(int n) {
memset(p, true, sizeof p);
p[0] = p[1] = false;
for (int i = 2; i <= n; i++) {
if (p[i]) {
primes.push_back(i);
for (int j = 2 * i; j <= n; j += i) p[j] = false;
}
}
}
int main() {
int n = 1e5;
do_primes(n); //预处理素数
for (int d = 1; d * 9 <= n; d++) { //从小到大枚举 公差
for (int i = 0; i < primes.size() && primes[i] + d * 9 <= n; i++) { //枚举首项
int k = 1, t = primes[i] + d;
while (t <= n && p[t]) {
t += d;
k++;
}
if (k == 10) { //有10项，则满足要求，则输出答案，退出程序
printf("%d\n", d);
exit(0);
}
}
}
return 0;
}
| 标题： | 2017年第八届蓝桥杯省赛-B.等差素数列 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/195 |
| 更新： | 2022-09-18 22:47:13 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |