企业官网建设流程全解析

前言

「等差素数列」指这样的素数序列：相邻两项的差恒定。例如3, 5, 7公差为 2，5, 11, 17, 23, 29公差为 6。题目通常要求「在某个上限之内，找出最长的等差素数列」，或者在给定项数时求出最小公差的数列。它看起来像纯数学题，实际实现涉及三个工程问题：素数表怎么打、搜索空间怎么剪、边界怎么防溢出。

常见误解有两个。第一，以为公差可以随便取奇数。除了 2 以外所有素数都是奇数，两个奇素数之差必然是偶数，所以在寻找长度大于 2 的数列时，公差只需要枚举偶数，搜索空间立刻减半。第二，以为「数列中每一项都小于等于上限」和「数列末项不超过上限」是同一件事——它们在循环边界上确实等价，但写代码时很容易把判断放在自增之后，导致访问越界。

本文先讲素数筛法，再讲如何从素数表里系统地枚举等差数列，最后给出完整的搜索与验证代码。示例以 C++17 为基准，不依赖第三方库。

一、先把素数表打出来

枚举等差素数列需要频繁判断「某个数是不是素数」。如果每次都试除到平方根，单次判断是 O(√n)，在搜索里会被调用很多次，整体代价难以接受。更合适的做法是用埃拉托斯特尼筛法（sieve of Eratosthenes）一次性打出上限以内的布尔表，之后每次判断是 O(1)。

筛法的原理很直接：从 2 开始，如果当前数没被标记为合数，它就是素数，把它所有大于等于自身平方的倍数标记为合数。从i * i开始而不是从2 * i开始，是因为更小的倍数已经被更小的素因子筛过了。

// 适用于 C++17
#include <cstddef>
#include <vector>

std::vector<bool> make_sieve(int limit) {
if (limit < 2) {
return {};
}
std::vector<bool> is_prime(static_cast<std::size_t>(limit) + 1, true);
is_prime[0] = false;
is_prime[1] = false;

for (int i = 2; static_cast<long long>(i) * i <= limit; ++i) {
if (!is_prime[static_cast<std::size_t>(i)]) {
continue;
}
// j 用 long long，避免 i * i 在 int 上溢出
for (long long j = static_cast<long long>(i) * i;
j <= limit; j += i) {
is_prime[static_cast<std::size_t>(j)] = false;
}
}
return is_prime;
}

两个细节必须注意。第一，内层循环的起点i * i要用long long计算：当limit接近INT_MAX时，i * i在int上会溢出，而有符号整数溢出是未定义行为，不是「得到一个负数」这么简单。第二，limit < 2时要提前返回，否则is_prime[1]越界。

std::vector<bool>是标准库里的特化版本，按位存储，节省空间，但它的operator[]返回的是代理对象而不是bool&，不能取地址，也不能传给需要bool*的接口。在本例中只做读写判断，没有影响；如果后续要把表传给 C 风格接口，应改用std::vector<char>。

二、枚举策略：固定首项与公差

最直接的枚举是「首项 a + 公差 d」两重循环：对每个素数 a、每个可能的 d，从 a 开始按 d 递增，统计连续素数的个数，直到超出上限或遇到合数。伪代码如下：

1. 
   
2. 对每个素数 a（a ≤ limit）。
3. 
   
4. 对每个公差 d（1 ≤ d，且 a + d ≤ limit）。
5. 
   
6. 令 v = a，长度 len = 1。
7. 
   
8. 当 v + d ≤ limit 且 v + d 是素数时，v += d，len += 1。
9. 
   
10. 用 len 更新最优解。
11. 
    

这个策略的正确性来自「等差数列由首项和公差唯一确定」。它的复杂度在最坏情况下是 O(N²) 量级（外层素数个数乘以公差个数，内层延伸的摊销较小），对于几千到几万的上限足够用；上限再大就需要更聪明的剪枝。

剪枝的核心是奇偶性。除 2 以外，素数都是奇数。若首项 a 是奇素数，公差 d 为奇数，则 a + d 是偶数且大于 2，必然是合数，数列长度最多为 2。因此当 a > 2 时只需枚举偶数 d。这一条能把搜索量减半，而且不改变结果。

// 适用于 C++17
#include <cstddef>
#include <vector>

struct Progression {
int start = 0;
int diff = 0;
int length = 0;
};

Progression longest_ap(const std::vector<bool>& is_prime, int limit) {
Progression best;
for (int a = 2; a <= limit; ++a) {
if (!is_prime[static_cast<std::size_t>(a)]) {
continue;
}
// a == 2 时公差可以是奇数；其余情况只看偶数公差
const int step = (a == 2) ? 1 : 2;
for (int d = step; a + d <= limit; d += step) {
int len = 1;
long long v = a;
while (v + d <= limit &&
is_prime[static_cast<std::size_t>(v + d)]) {
v += d;
++len;
}
if (len > best.length) {
best = Progression{a, d, len};
}
}
}
return best;
}

这里v用long long，是为了让v + d的中间结果不溢出。虽然循环条件已经保证a + d <= limit，但在内层延伸时v会不断增大，用更宽的类型计算加法是低成本的保险。

如果题目要求「长度至少为 k 的最小末项」或「给定长度下最小的公差」，只需把更新最优解的条件改掉，搜索框架不变。若要求输出所有达到最优长度的数列，就把单个best换成std::vector<Progression>，在len > best.length时清空再追加，在len == best.length时追加。

三、完整示例

下面把筛法与搜索拼起来，求 1000 以内最长的等差素数列。为了便于观察，同时打印该数列的各项。

// 适用于 C++17
#include <cstddef>
#include <iostream>
#include <vector>

std::vector<bool> make_sieve(int limit) {
if (limit < 2) return {};
std::vector<bool> is_prime(static_cast<std::size_t>(limit) + 1, true);
is_prime[0] = false;
is_prime[1] = false;
for (int i = 2; static_cast<long long>(i) * i <= limit; ++i) {
if (!is_prime[static_cast<std::size_t>(i)]) continue;
for (long long j = static_cast<long long>(i) * i;
j <= limit; j += i) {
is_prime[static_cast<std::size_t>(j)] = false;
}
}
return is_prime;
}

struct Progression {
int start = 0;
int diff = 0;
int length = 0;
};

Progression longest_ap(const std::vector<bool>& is_prime, int limit) {
Progression best;
for (int a = 2; a <= limit; ++a) {
if (!is_prime[static_cast<std::size_t>(a)]) continue;
const int step = (a == 2) ? 1 : 2;
for (int d = step; a + d <= limit; d += step) {
int len = 1;
long long v = a;
while (v + d <= limit &&
is_prime[static_cast<std::size_t>(v + d)]) {
v += d;
++len;
}
if (len > best.length) {
best = Progression{a, d, len};
}
}
}
return best;
}

int main() {
const int limit = 1000;
const std::vector<bool> table = make_sieve(limit);
const Progression p = longest_ap(table, limit);

std::cout << "start=" << p.start
<< " diff=" << p.diff
<< " length=" << p.length << '\n';

long long v = p.start;
for (int i = 0; i < p.length; ++i, v += p.diff) {
std::cout << v << (i + 1 == p.length ? '\n' : ' ');
}
return 0;
}

按代码逻辑推演，输出会给出首项、公差与长度，再按等差数列展开各项。需要注意，当上限较小时，可能存在多条长度相同但首项不同的数列，上面的实现只保留第一条被扫描到的（首项最小、同首项下公差最小）。如果题目要求「所有最优解」，必须改成分组收集，而不是只记一个。

验证结果时不要只信程序输出。可以手工检查几个点：数列中每一项是否都在素数表里；相邻差是否等于diff；末项加diff是否超出上限或为合数。对于已知的小例子，3, 5, 7是上限 10 以内的最长数列（长度 3），5, 11, 17, 23, 29的公差是 6、长度是 5。另有一个常被引用的例子：首项 7、公差 30 的数列7, 37, 67, 97, 127, 157，六项都是素数。这些可以作为边界测试用例。

四、复杂度与适用范围

上限达到 10⁷ 以上时，两重循环会明显变慢。可行的优化包括：只在素数之间枚举首项；对每个首项，用「下一个素数」跳着找公差，而不是逐个偶数尝试；或者反过来固定公差、扫描整个素数表。哪种更快取决于数据分布，应当用std::chrono::steady_clock测量本机耗时，而不是凭直觉下结论——不同实现、不同上限下的相对优劣可能相反。

数学上还有一层背景：狄利克雷定理（Dirichlet's theorem）保证，只要首项与公差互素，该等差数列中就含有无穷多个素数。但它不保证「连续若干项都是素数」，所以有限范围内的最长数列仍然只能靠搜索确定。Green-Tao 定理说明素数中存在任意长的等差数列，但那是存在性结论，构造性的搜索依然受上限约束。

常见坑点

坑点一：筛法内层从2 * i开始。

❌for (int j = 2 * i; j <= n; j += i)，做了大量重复标记。

✅ 从i * i开始，并用long long计算，避免溢出。

坑点二：i * i用 int 计算。

❌for (int i = 2; i * i <= n; ++i)，当 n 接近INT_MAX时溢出，属于 UB。

✅ 写成static_cast<long long>(i) * i <= n。

坑点三：把 1 当成素数。

❌ 筛法只把下标 0 置 false，忘记is_prime[1] = false;。

✅ 初始化后显式把 0 和 1 都设为 false。

坑点四：对所有首项都枚举奇数公差。

❌for (int d = 1; ...; d += 1)，大量无效尝试。

✅ 首项大于 2 时公差只取偶数，长度最多为 2 的奇数公差可直接跳过。

坑点五：内层判断顺序写反。

❌while (is_prime[v + d] && v + d <= limit)，先越界访问再判断边界。

✅ 先判断v + d <= limit，再查表；&& 的短路求值顺序不能依赖错误写法。

坑点六：用int累加数列末项。

❌int v = a; v += d;在接近上限且 d 较大时溢出。

✅ 用long long保存当前项，或在每次加法前检查上界。

坑点七：只保留一个最优解却声称输出了全部。

❌ 题目要求所有最长数列，代码只记录第一条。

✅ 用容器收集，按长度分组，注意清空旧结果。

总结

求等差素数列的代码不长，难点集中在边界：i * i的溢出、v + d的越界、终止符与上限的比较顺序。把这三处写对，再用几个已知的小数列做对照，结果就是可信的。至于更大的上限，那属于筛法与搜索策略的优化问题，先保证正确，再谈速度。