前言「等差素数列」指这样的素数序列相邻两项的差恒定。例如3, 5, 7公差为 25, 11, 17, 23, 29公差为 6。题目通常要求「在某个上限之内找出最长的等差素数列」或者在给定项数时求出最小公差的数列。它看起来像纯数学题实际实现涉及三个工程问题素数表怎么打、搜索空间怎么剪、边界怎么防溢出。常见误解有两个。第一以为公差可以随便取奇数。除了 2 以外所有素数都是奇数两个奇素数之差必然是偶数所以在寻找长度大于 2 的数列时公差只需要枚举偶数搜索空间立刻减半。第二以为「数列中每一项都小于等于上限」和「数列末项不超过上限」是同一件事——它们在循环边界上确实等价但写代码时很容易把判断放在自增之后导致访问越界。本文先讲素数筛法再讲如何从素数表里系统地枚举等差数列最后给出完整的搜索与验证代码。示例以 C17 为基准不依赖第三方库。一、先把素数表打出来枚举等差素数列需要频繁判断「某个数是不是素数」。如果每次都试除到平方根单次判断是 O(√n)在搜索里会被调用很多次整体代价难以接受。更合适的做法是用埃拉托斯特尼筛法sieve of Eratosthenes一次性打出上限以内的布尔表之后每次判断是 O(1)。筛法的原理很直接从 2 开始如果当前数没被标记为合数它就是素数把它所有大于等于自身平方的倍数标记为合数。从i * i开始而不是从2 * i开始是因为更小的倍数已经被更小的素因子筛过了。// 适用于 C17#include cstddef#include vectorstd::vectorbool make_sieve(int limit) {if (limit 2) {return {};}std::vectorbool is_prime(static_caststd::size_t(limit) 1, true);is_prime[0] false;is_prime[1] false;for (int i 2; static_castlong long(i) * i limit; i) {if (!is_prime[static_caststd::size_t(i)]) {continue;}// j 用 long long避免 i * i 在 int 上溢出for (long long j static_castlong long(i) * i;j limit; j i) {is_prime[static_caststd::size_t(j)] false;}}return is_prime;}两个细节必须注意。第一内层循环的起点i * i要用long long计算当limit接近INT_MAX时i * i在int上会溢出而有符号整数溢出是未定义行为不是「得到一个负数」这么简单。第二limit 2时要提前返回否则is_prime[1]越界。std::vectorbool是标准库里的特化版本按位存储节省空间但它的operator[]返回的是代理对象而不是bool不能取地址也不能传给需要bool*的接口。在本例中只做读写判断没有影响如果后续要把表传给 C 风格接口应改用std::vectorchar。二、枚举策略固定首项与公差最直接的枚举是「首项 a 公差 d」两重循环对每个素数 a、每个可能的 d从 a 开始按 d 递增统计连续素数的个数直到超出上限或遇到合数。伪代码如下对每个素数 aa ≤ limit。对每个公差 d1 ≤ d且 a d ≤ limit。令 v a长度 len 1。当 v d ≤ limit 且 v d 是素数时v dlen 1。用 len 更新最优解。这个策略的正确性来自「等差数列由首项和公差唯一确定」。它的复杂度在最坏情况下是 O(N²) 量级外层素数个数乘以公差个数内层延伸的摊销较小对于几千到几万的上限足够用上限再大就需要更聪明的剪枝。剪枝的核心是奇偶性。除 2 以外素数都是奇数。若首项 a 是奇素数公差 d 为奇数则 a d 是偶数且大于 2必然是合数数列长度最多为 2。因此当 a 2 时只需枚举偶数 d。这一条能把搜索量减半而且不改变结果。// 适用于 C17#include cstddef#include vectorstruct Progression {int start 0;int diff 0;int length 0;};Progression longest_ap(const std::vectorbool is_prime, int limit) {Progression best;for (int a 2; a limit; a) {if (!is_prime[static_caststd::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_caststd::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::vectorProgression在len best.length时清空再追加在len best.length时追加。三、完整示例下面把筛法与搜索拼起来求 1000 以内最长的等差素数列。为了便于观察同时打印该数列的各项。// 适用于 C17#include cstddef#include iostream#include vectorstd::vectorbool make_sieve(int limit) {if (limit 2) return {};std::vectorbool is_prime(static_caststd::size_t(limit) 1, true);is_prime[0] false;is_prime[1] false;for (int i 2; static_castlong long(i) * i limit; i) {if (!is_prime[static_caststd::size_t(i)]) continue;for (long long j static_castlong long(i) * i;j limit; j i) {is_prime[static_caststd::size_t(j)] false;}}return is_prime;}struct Progression {int start 0;int diff 0;int length 0;};Progression longest_ap(const std::vectorbool is_prime, int limit) {Progression best;for (int a 2; a limit; a) {if (!is_prime[static_caststd::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_caststd::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::vectorbool 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 以内的最长数列长度 35, 11, 17, 23, 29的公差是 6、长度是 5。另有一个常被引用的例子首项 7、公差 30 的数列7, 37, 67, 97, 127, 157六项都是素数。这些可以作为边界测试用例。四、复杂度与适用范围环节复杂度说明筛法建表O(N log log N)空间 O(N) 位暴力枚举首项与公差O(P·N) 最坏P 为素数个数内层延伸摊销后远小于理论值单次素数判断O(1)查表试除判断对照O(√n)仅在内存受限时使用上限达到 10⁷ 以上时两重循环会明显变慢。可行的优化包括只在素数之间枚举首项对每个首项用「下一个素数」跳着找公差而不是逐个偶数尝试或者反过来固定公差、扫描整个素数表。哪种更快取决于数据分布应当用std::chrono::steady_clock测量本机耗时而不是凭直觉下结论——不同实现、不同上限下的相对优劣可能相反。数学上还有一层背景狄利克雷定理Dirichlets 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_castlong 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起步用long long防溢出枚举首项取素数公差按奇偶性剪枝延伸先判上界再查表当前项用宽类型记录明确是「一条最优」还是「全部最优」验证手工核对小例子与边界求等差素数列的代码不长难点集中在边界i * i的溢出、v d的越界、终止符与上限的比较顺序。把这三处写对再用几个已知的小数列做对照结果就是可信的。至于更大的上限那属于筛法与搜索策略的优化问题先保证正确再谈速度。
