题目理解

我们需要在连续的质数序列中找到一个区间 $[L, R]$，使得区间内所有质数的和等于给定的 $N$。

算法思路分析

整体策略

代码采用双指针滑动窗口结合分段筛法的策略：

1. 先用普通筛法处理小范围质数
2. 在小范围质数中寻找解
3. 如果没找到，在大范围中使用分段筛法继续寻找

代码结构分析

1. 埃拉托斯特尼筛法

void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) p.push_back(i);
        for (int j = 0; j < p.size() && i * p[j] <= n; j++) {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}

这是线性筛法，时间复杂度 $O(n)$，空间复杂度 $O(n)$。

2. 主要求解函数

void solve(long long K) {
    long long sum = 0;
    for (int i = 0, j = 0; i < p.size(); i++) {
        sum += p[i];
        while (sum > K && j <= i) sum -= p[j++];
        if (sum == K) {
            cout << p[j] << " " << p[i] << "\n";
            exit(0);
        }
    }
}

这是标准的滑动窗口算法：

• i 是右指针，不断扩展窗口
• j 是左指针，当和超过 $K$ 时收缩窗口
• 时间复杂度：$O(n)$

3. 分段筛法函数

void calc(int c, long long K) {
    long long mid = K / c;
    long long L = max(2ll, mid - c * 50);
    long long R = mid + c * 50;
    // 分段筛质数
    // 再次使用滑动窗口寻找解
}

当小范围质数找不到解时，在 $K/c$ 附近的大范围中寻找：

• 假设解的长度约为 $c$
• 在 $[K/c - 50c, K/c + 50c]$ 范围内筛质数
• 再次使用滑动窗口

算法正确性分析

为什么这样设计？

1. 小范围优先：大多数解可以在 $10^8$ 以内的质数中找到
2. 分段筛法：对于大 $N$，解可能出现在大质数区间，但无法一次性筛出所有质数
3. 启发式搜索：假设解的长度不会太大（最多500），在可能区间内搜索

数学依据

• 前 $k$ 个质数的和约为 $O(k^2 \log k)$
• 对于大 $N$，解的长度大约为 $O(\sqrt{N/\log N})$
• 代码中限制长度最多500是合理的启发式

时间复杂度分析

1. 线性筛法：$O(10^8)$
2. 滑动窗口：$O(\text{质数个数})$
3. 分段筛法：最多500次，每次筛 $O(100c)$ 的范围
4. 总体：在可接受范围内

算法标签

• 数学/数论：涉及质数性质和分布
• 质数筛法：埃拉托斯特尼筛法和分段筛法
• 滑动窗口/双指针：在质数序列中寻找和为定值的区间
• 启发式搜索：基于解的长度限制搜索范围

示例验证

样例1：$N = 15$

质数序列：2, 3, 5, 7, 11, 13, ...
滑动窗口过程：
i=0: sum=2
i=1: sum=5
i=2: sum=10
i=3: sum=17 > 15, 收缩：j=0, sum=15
找到解：3 + 5 + 7 = 15
输出：3 7

样例4：$N = 10^9 + 7$

这是一个质数本身，所以解就是 $[10^9+7, 10^9+7]$

代码优化点

1. 提前终止：找到解立即退出
2. 范围控制：分段筛法只在必要范围内进行
3. 长度限制：最多搜索长度为500的解，基于数学启发式

可能的问题

对于某些特殊的 $N$，如果解的长度超过500或者出现在很特殊的区间，可能找不到解。但根据质数分布理论，这种情况很少见。

这份代码巧妙地结合了多种算法，能够在 $N$ 达到 $10^{11}$ 时仍然有效工作。