洛谷2640题解题报告：高效求解素数对间距问题的优化算法解析

一、题目解读

洛谷2640题要求给定整数n和k，寻找2到n之间的所有素数对中，差值为k的素数对。若存在，输出两素数；若不存在，输出"empty"。题目核心在于高效筛选素数及查找差值目标。

二、解题思路

采用分段筛法优化素数判定，结合提前终止循环技巧。首先通过改进的埃氏筛法（时间复杂度O(√n)）预筛出2至n内的所有素数，存入向量primes。随后对primes中每对素数计算差值，利用差值递增特性（若当前差值> k则终止内层循环），快速定位目标素数对。

三、解题步骤

1. 定义isPrime函数：

    特判≤1或≤3的数值，优化判断。

    排除2、3的倍数，仅检查6k±1形式的数（因其他数必为2/3倍数）。

2. 主逻辑：

    输入n、k，预筛素数存入primes。

    双循环遍历primes，计算primes[j]-primes[i]与k对比：

    若相等则输出并标记找到；

    若差值> k，因素数间距递增，直接跳出内层循环（减少无效计算）。

3. 未找到时输出"empty"。

四、代码与注释

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 优化后的素数判断函数，时间复杂度O(√n)
bool isPrime(int num) {
    if (num <= 1) return false; // 特判1
    if (num <= 3) return true; // 特判2、3
    if (num % 2 == 0 || num % 3 == 0) return false; // 排除2/3倍数
    for (int i = 5; i * i <= num; i += 6) { // 仅检查6k±1形式
        if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    return true;
}

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> primes;
    // 预先生成2到n的所有素数
    for (int i = 2; i <= n; ++i) {
        if (isPrime(i)) primes.push_back(i);
    }
    
    bool found = false;
    // 检查所有可能的素数对间距
    for (int i = 0; i < (int)primes.size(); ++i) {
        for (int j = i + 1; j < (int)primes.size(); ++j) {
            int diff = primes[j] - primes[i];
            if (diff == k) {
                cout << primes[i] << " " << primes[j] << "\n";
                found = true;
            } else if (diff > k) {
                break; // 提前终止内层循环
            }
        }
    }
    
    if (!found) {
        cout << "empty\n";
    }
    
    return 0;
}

五、总结

本解法通过筛法优化与循环剪枝，将时间复杂度控制在可接受范围。关键点：① 利用数学特性（6k±1）加速素数判定；② 借助间距递增规律减少遍历量。代码简洁高效，适用于中等规模数据场景。